Piero Scaruffi(Copyright © 2013 Piero Scaruffi | Legal restrictions )
These are excerpts and elaborations from my book "The Nature of Consciousness"
The Turing Machine
The two great visionaries of computation, the British mathematician Alan Turing and the Hungarian mathematician John Von Neumann, had a number of influential ideas. Among the many, in 1936 Turing formalized how a machine can perform logical calculus ("On computable numbers, with an application to the Entscheidungsproblem", 1936), and, a few years later, Von Neumann explored the possibility that a machine could be programmed to make a copy of itself. In other words, Turing laid the foundations for the discipline of building an “intelligent” machine, and Von Neumann laid the foundations for the discipline of building a self-reproducing machine.
Turing defined computation as the formal manipulation of symbols through the application of formal rules (Hilbert's view of Logic), and devised a machine (“On Computable Numbers, with an Application to the Entscheidungsproblem”, 1936) that would be capable of performing any type of computation (Hilbert's dream).
Hilbert's ideas can be expressed in terms of mathematical "functions". A predicate can always be made to correspond to a function. For example, “age(Person,Number)” corresponds to the function “Number= age(person)”; and viceversa. Both mean that the age of Person is Number. The advantage of using functions instead of predicates is that it is easier to manipulate functions than predicates. For example, the US mathematician Alonzo Church showed how two functions can be compared. A function can be defined in an “extensional” way (the pairs of input and output values) or in an “intensional” way (the computational procedure it performs). Comparing two extensional definitions can take forever (there can be infinite pairs of input and output). In order to compare two intensional definitions, Church invented the “Lambda abstraction”, which provides rules to transform any function in a “canonical” form. Once they are in canonical form, two functions can be easily compared.
In the language of functions, Hilbert's goal was to find a mechanical procedure to build all computable (or “recursive”) functions. So a recursive function is defined by an algorithm, which in turn can be implemented by a computer program. Recursive functions correspond to programs of a computer. Not surprisingly, it turns out that a predicate is decidable (can be proven true or false) if and only if the corresponding function is recursive, i.e. computable.
Turing realized this and, when he set himself to find a mechanical procedure to perform logical proofs, he basically set himself to invent the computer (at least conceptually). His thought experiment, the “Turing Machine”, is the algorithm that Hilbert was looking for, and it turns out that it is also the general algorithm that fuels electronic computers.
A Turing Machine is capable of performing all the operations that are needed to perform logical calculus: read current symbols, process them, write new symbols, examine new symbols. Depending on the symbol that it is reading and on the state in which it is, the Turing machine decides whether it should move on, turn backwards, write a symbol, change state or stop. Turing's machine is an automatic formal system: a system to automatically compute an alphabet of symbols according to a finite set of rules.
Church argued that everything that is computable in nature can be computed with a Turing machine.
But there can be infinite Turing machines, depending on the rules to generate new symbols. So Turing described how to build a machine that would simulate all possible Turing machines.
The "Universal Turing Machine" is a Turing Machine capable of simulating all possible Turing Machines. It contains a sequence of symbols that describes the specific Turing machine that must be simulated. For each computational procedure, the universal machine is capable of simulating a machine that performs that procedure. The universal machine is therefore capable of computing any computational function. In other words, since the Universal Turing Machine is a machine capable of performing any other machine, it is capable of solving all mathematical problems. A computer is nothing but a Turing machine with a finite memory.
When Von Neumann neatly divided the data from the instructions (instructions are executed one at the time by the “processor” and they operate on data kept in a “memory”), he simply interpreted for engineers the concepts of the Universal Turing Machine: a computer (the hardware) can solve any problem if it is fed the appropriate program (the software). That architecture was to become the architecture of the computer and today’s “sequential” computers (the most common varieties) are still referred to as “Von Neumann architectures”. They are “sequential” in the sense that they are controlled by software programs and execute one instruction after the other from those programs.
Ultimately, Turing reduced Hilbert’s program to manipulation of symbols: logic is nothing more than symbol processing. Indirectly, he turned the computer into the culminating artifact of Hilbert’s formal program.
Turing showed that rational machines are feasible. Furthermore, he showed that one can build a rational machine that can perform "any" rational task.
As for Hilbert’s decision problem, both Church and Turing had basically offered a definition of “algorithm” (one based on Lambda Calculus and the other one based on the Turing machine), both definitions being equivalent and both showing that Hilbert’s question could not be answered: there is no universal algorithm to solve every mathematical problem, or there is no universal algorithm for deciding whether or not a Turing machine will stop. Turing’s argument was very similar to Goedel’s incompleteness theorem whereas Alonzo Church had already come up with his own proof that first order logic is undecidable (“An unsolvable problem of elementary number theory”, 1935).
Later the Israeli physicist David Deutsch generalized Turing's ideas and envisioned a "quantum" machine in which Turing states can be linear combinations of states (“Quantum Theory, The Church-Turing Principle And The Universal Quantum Computer”, 1985). The behavior of a quantum machine is a linear combination of the behavior of several Turing machines. A quantum machine can only compute recursive functions, just like Turing's machine, but it turns out to be much faster in solving problems that exhibit some level of parallelism. In a sense, a quantum computer is capable of decomposing a problem and delegating the sub-problems to copies of itself in other universes.
Back to the beginning of the chapter "Machine Intelligence" | Back to the index of all chapters