|
|
|
|
|
|||
|
|
|
|
In 1935 Turing thought up the abstract machine nowadays known simply as the universal Turing machine. This consists of a limitless memory in which both program and data are stored, and a scanner that moves back and forth through the memory, symbol by symbol, reading what it finds and writing further symbols. Each of the machine's basic actions is very simple. Examples are 'identify the symbol on which the scanner is positioned', 'write 0', 'write 1', 'move one position to the left' and 'move one position to the right'. Complexity of operation is achieved by the chaining together of large numbers of these simple basic actions. Despite the universal Turing machine's austere simplicity, it will carry out any task that can be carried out by the most powerful of today's computers.
The first electronic stored-program digital computers came into existence
in the late 1940s and early 1950s, including the very fast Pilot
Model ACE, built largely to Turing's design at the National Physical Laboratory.
All were modelled on the universal Turing machine, and today's digital computers
also are in essence universal Turing machines—program and data are both
stored in digital form in the same internal memory, complexity is achieved
by massive iteration of a small number of very simple basic actions, and universality
of function is emphasized.
Turing's aim in 1935 was to devise a machine, as simple as possible, that
is capable of performing any calculation that can be performed by a human
mathematician who has unlimited time and energy, an unlimited supply of paper
and pencils, and perfect concentration, and is working in accordance with
some algorithmic or 'rule-of-thumb' method. To call a machine 'universal'
is just to say that it is capable of carrying out all such calculations. Modern
digital computers have the inherited characteristic of being imitators of
a human being engaged in rule-of-thumb calculation. As Turing himself wrote
in his programming manual for
the Ferranti Mark I computer, 'Electronic computers are intended to carry
out any definite rule-of-thumb process which could have been done by a human
operator working in a disciplined but unintelligent manner'.
An intriguing question arises. If we set aside the traditional idea that digital
information-processing machines are to be modelled on human mathematicians
working in a rule-of-thumb manner, can we devise machinery that is capable
of accomplishing a wider variety of tasks than the universal Turing machine?
The answer is that such machines can be described on paper - but at the present
time noone knows whether it will be possible to create one. Computers of this
sort are hypermachines and the associated field of hypercomputation
is attracting a growing number of researchers ('hyper' meaning 'more than
normal'). Some speculate that the human brain itself - the most complex information-processor
known - is a naturally-occurring example of a hypermachine.
Prior to the recent surge of interest in hypercomputation, any information-processing
task known to be too difficult for the universal Turing machine was written
off as 'uncomputable', and it is in that sense that a hypermachine 'computes
the uncomputable'. Examples of tasks that defeat the universal Turing machine
are to be found in even the most straightforward areas of mathematics. Pick
a statement of simple arithmetic at random and input it to the universal Turing
machine. The statement may be one that follows from the fundamental axioms
of arithmetic - that is to say, a theorem - or it may be a non-theorem.
0=0 and 7+5=12 are examples of theorems, 0=1 and 'every number is the sum
of two even numbers' of non-theorems. The universal Turing machine cannot
say correctly, of every arithmetical statement which could be given to it,
whether the statement is a theorem or a non-theorem.
Another example, from Euclidean geometry, involves what are called 'tiles'—squares
with coloured edges, and possibly other markings. A 'tiling set' is any finite
collection of tiles.
Example of a tiling set
A given tiling set is said to 'tile the plane' if the Euclidean plane can be covered with copies of the tiles in the set, without gaps or overlaps, and in such a way that adjoining edges are always of the same colour (and other markings on the tiles, if any, match up in specified ways).
A tiling of the plane using the above tiling set
The logicians William Hanf and Dale Myers have established the remarkable result that there are tiling sets which will tile the plane only in patterns so complicated that the universal Turing machine cannot always tell, given a tile and a position in the pattern, whether or not that tile belongs there.
Theoretical computer science also offers examples of tasks that are too hard
for the universal Turing machine. One is the
terminating program task, or TP task. The fact that the universal Turing
machine cannot carry out the TP task is sometimes expressed by saying that
no general-purpose programming language (Pascal, BASIC, Prolog or C, for example)
can be supplied with a 'crash debugger'—a tool that spots all bugs that
could lead to crashes, including bugs that produce infinite loops.
Turing himself was the first to investigate the idea of machines that are
able to perform mathematical tasks too difficult for the universal Turing
machine (this was in 1938, in his PhD thesis). He described these as 'a new
kind of machine' and called them O-machines.
An O-machine is the result of augmenting the universal Turing machine with
a black box, or 'oracle'. The black box is able to carry out the TP task,
or some related task. O-machines are in other respects similar to ordinary
computing machinery. A digitally encoded program is fed in and the machine
produces digital output from digital input by means of a step-by-step procedure.
This step-by-step procedure consists of repeated applications of the machine's
basic or 'hard-wired' operations, one of which is to pass data to the oracle
and register the oracle's response.
Turing said nothing about how an oracle might carry out its task. However, machinery that fulfils the specifications of an O-machine's black box is not hard to concoct on paper. Two examples of notional mechanisms that perform the TP task are outlined in the reference article Some Notional Hypercomputers.
In the exotic mathematical theory of hypercomputation, tasks such as the ones
just mentioned are no longer uncomputable. Even a debugger that can tell,
of any program in a language for an ordinary computer, whether the program
will enter an infinite loop is a theoretical possibility. If hypermachines
can be built—and it's a big if— the potential for solving
hitherto intractable mathematical problems will be enormous. The mathematics
that can be done by means of the universal Turing machine is a relatively
tiny drop in an infinite ocean. Computer science may be approaching one of
its most significant advances since the first electronic embodiments of the
universal Turing machine were wired together. On the other hand, the project
may simply fizzle out for want of some means of realizing an oracle. The search
for suitable physical, chemical, or biological phenomena is getting under
way. Perhaps the answer will be complex molecules, or other structures, that
link together in patterns as complicated as those discovered by Hanf and Myers.
Or perhaps, as suggested by Jon Doyle of MIT, there may be naturally-occurring
equilibrating systems, with discrete spectra, that can be seen as carrying
out an 'uncomputable' task, equilibrating to the 'answer' (1 or 0, for example)
after being bombarded with input.
Outside of mathematical logic, Turing's work on O-machines has largely been
forgotten. Ironically, a myth has taken root in mainstream cognitive and computer
science, and also in Artificial Intelligence and Artificial Life, according
to which Turing demonstrated in his work during 1935-1936 that hypermachines
are impossible! Turing and
Alonzo Church (Turing's PhD adviser) are mistakenly credited with having
enunciated a principle to the effect that the universal Turing machine can
simulate the behaviour of any other machine. This principle, widely but incorrectly
known as the Church-Turing thesis, implies that no machine can carry out an
information-processing task that lies beyond the scope of the universal Turing
machine. In reality, Turing and Church claimed only that the universal Turing
machine can simulate the behaviour of any human mathematician who is working
with paper and pencil in accordance with an algorithmic method - a considerably
weaker claim, which certainly does not rule out the existence of a hypermachine.
Unfortunately, Turing's pioneering theoretical work in this area has been
forgotten even among those pursuing the goal of building a hypermachine. A
recent review of this emerging field speaks of these machines as 'falling
outside Turing's conception' and says that they are 'computers of a type never
envisioned by Turing'. Researchers in the area talk of carrying out information-processing
'beyond the Turing limit' and describe themselves as attempting to 'break
the Turing barrier'.
Turing Archive Catalogue || Catalogue of Reference Articles || The Turing Archive Homepage
Site maintained by Jack Copeland and Gordon Aston
