Google Play icon

Scientists provide new and universal definition for computing

Posted May 8, 2014

While reading the writings of one of the pioneers in the field of computer science, Alan Turing, one may notice that the word “computer” stands not for a physical device but for “someone who computes”. Even though the semantics of the term in question is different today, the precise mathematical, logical and algorithmic definition of what a computation really is, is still lacking.

The computer, originally called Harwell but now called the Wolverhampton Instrument for Teaching Computing from Harwell (WITCH), was originally powered up in 1951 (pictured above). Between 1952 and 1957 the computer was used for early atomic research. It is also one of examples what computing systems used to be. Image source: itst/Flickr, CC BY-SA 2.0

Figure 1. The computer, originally called Harwell but now called the Wolverhampton Instrument for Teaching Computing from Harwell (WITCH), was originally powered up in 1951 (pictured above). Between 1952 and 1957 the computer was used for early atomic research. It is also one of examples what computing systems used to be. Image source: itst/Flickr, CC BY-SA 2.0

A computer is essentially a physical system that manipulates abstract concepts, but how are the two domains related is not a trivial matter. Today one also hears about the development of quantum, as well as chemical, DNA and other forms of nonconventional computing. Such a big range of physical systems that are able to perform computations has led some to conclude that our whole universe is a computer itself. Inspired by the debate, a group of researchers set out to produce a definition of computation – that is, sufficient and necessary conditions for a physical system to be called a computer.

“We can all agree that a laptop running a Matlab calculation and a server processing search engine queries are physical systems performing computation. However, when we move beyond standard and mass-produced technology, the question becomes more difficult to answer”, the researchers say. As an example, is human brain a computer? Does a plant perform any computations when it tends toward the most optimal shape? In some sense, any physical process is a sort of computation. But setting with the statement that “all physical systems do compute”, according to the researchers, is trivial, for the statement is then stripped of its informative content.

In order for a computation to take place, the constituents of a physical system and the relations among them must be represented in mathematical or logical language. Hence, an abstract representation of a physical system is required. In quantum mechanics, for example, an electron is represented as a wavefunction, and this representation allows for various conclusions to be drawn by means of logical and mathematical reasoning.

The question to be answered is: “How is the representation relation established, given that abstract representation and the physical system it represents are inherently asymmetric – one can devise any kind of abstract model one likes, yet there is no a priori reason to suppose that it will be instantiated by some physical system?” For this reason it is not sufficient to say that a physical-abstract system pair is enough for computation. It is crucial to give an account as to how the abstract represents the physical.

Although the relation between the abstract and the physical is a matter of age-long philosophical debate, researchers’ aim was to give an account that would prove useful to scientists working in the field first and foremost. One of the most usual forms of abstract representation is modelling. In physics, for example, models are created and then tested experimentally to verify them. Models are not isolated: they emerge from within certain theories. As an example, an electron, represented as a wavefunction in quantum mechanics, is also represented as a point-mass in classical mechanics and as a vector and quantum field theory. Therefore, models are theory-dependent, and the theories from which they emerge determine abstract relations between concepts.

Another thing to note is that physical systems evolve and for this reason it is not enough to give a representation of a physical system but it is also necessary to compare the representations of its different states from within the representational model. When an experiment is conducted on a physical system, the test apparatus and the physical system to be tested are given representations in the model. A representation then undergoes “changes” within the model itself – for example by being fed to a dynamical function and by measuring its output considered as a different state. The output is then compared to the model-representation of the output state of the physical system. If the output representation and the representation of the output happen to match, the model is said to be adequate. For a graphical explanation see Figure 2.

Figure 1: M'(P) is output representation; M(P') is representation of an output. If the two are equivalent, model is said to be correct. Image credit: Clare Horsman et al.

Figure 2: M'(P) is output representation; M(P’) is representation of an output. If the two are equivalent, model is said to be correct. Image credit: Clare Horsman et al.

If the diagram described above commutes, that is, if the representation of the output state is equivalent to the output of the function modelling the changes undergone by the physical system, one can deduce that the model suitably predicts evolution of the physical system. Two options are available at this point – if the aim of the modelling is an abstract prediction, the process of establishing the representation relationship is done. However, if the question is which physical system corresponds the model – assuming there is one – several physical systems and their evolutions have to be tested and compared to match the abstract model-output. Technology and engineering come in handy at this point, for it is by devising physical systems themselves that the match can be discovered. As an example, given a representation of a primitive electronic device and a model-output of some function, one can test what physical configuration of a device would produce an end state that would correspond to the output in question.

Herein lies the essence of computation: computers are physical systems whose states correspond to abstract concepts and whose physical evolutions correspond to abstract functions. Thus if we want a physical system such as a smartphone to do arithmetic for us, we must establish correspondence between numbers and the physical states of a smartphone, as well as between arithmetic operations and changes that the internals of a smartphone may undergo. The researchers emphasize that such correspondence is a matter of choice: “For example, system designers in a standard semi-conductor-based computer chose the modelling representation ‘voltage high → 1, voltage low → 0’.” What is important is to make these representations easily reversible, so that one can flawlessly match physical states with abstract concepts.

Hence, experimentation begins from abstract modelling and predicts physical states of a test system, whereas computation begins from the same, encodes abstract concepts in the initial states that they represent, and predicts abstract concepts corresponding to the end states of a physical system. “This is physical computing: the use of a physical system to predict the outcome of an abstract evolution”, the researchers conclude.

A notable aspect of the presented framework is the importance of the transfer between abstract and physical domains – the encoding of abstract concepts in a physical system and decoding of physical states back into abstract terms. Someone has to do the encoding/decoding and for this reason a computing system requires an agent. If such an agent is absent, the system is not a computer. However, the agent need not be human, it can also be artificial intelligence that does not do the computations itself but relies on an external physical system that encodes and decodes in a manner distinguishable to the agent.

The framework also allows to easily deny the suggestion that “everything is computation”. Given the hypothesis that the whole universe is one universal computer, the supposed computing system is lacking a computing agent capable of encoding and decoding between abstract and physical domains. Since there is no such agent, not everything is a computation and, according to the framework, the universe cannot be a computer.

Source article: arXiv: 1309.7979v2 [cs.ET] 7 Mar 2014

Featured news from related categories:

Technology Org App
Google Play icon
84,947 science & technology articles

Most Popular Articles

  1. New Class of Painkillers Offers all the Benefits of Opioids, Minus the Side Effects and Addictiveness (October 16, 2019)
  2. Plastic waste may be headed for the microwave (5 days old)
  3. "Helical Engine" Proposed by NASA Engineer could Reach 99% the Speed of Light. But could it, really? (6 days old)
  4. How social media altered the good parenting ideal (September 4, 2019)
  5. What's the difference between offensive and defensive hand grenades? (September 26, 2019)

Follow us

Facebook   Twitter   Pinterest   Tumblr   RSS   Newsletter via Email