Inquire about purchasing the book | Table of Contents | Annotated Bibliography | Class on Nature of Mind

**These are excerpts and elaborations from my book "The Nature of Consciousness"**

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 |