Information Technology Reference
In-Depth Information
U
is simple to describe but complicated to write down in detail. The Universal
Turing Machine
U
must imitate
T
step-by-step, keeping a record of the state of
T
T's tape at each stage. By examining its simulated input tape
t
, the machine can
see what
T
would read at any given stage. Then, by looking at the description
it has of
T
,
U
can find out what
T
is supposed to do next. This is essentially just
what we would do when using a list of quintuples and a tape to figure out what
a Turing machine does. Turing's universal machine
U
is just a slower version
of us!
Turing went into great detail to prove the existence of a Universal Turing
Machine and, as you can see in
Figure 6.5
, the resulting state transition dia-
gram for
U
is much more complicated than that for our simple Parity Counter
(
Fig. 6.10
) that we describe in detail later. This example, from MIT computer
scientist Marvin Minsky, makes use of eight symbols and twenty-three states.
Most digital computers built today are effectively universal computers. With
the right program, enough time, and enough memory, any universal computer
can simulate any other computer.
If we ignore the slowness and inefficiency of using a Turing machine,
we can ask this fundamental question: what problems can be solved by
such a machine? The answer is very surprising. Everything that is algorith-
mically computable is computable by a Turing machine. Why should we
believe this? At around the same time as Turing was devising his ingenious
machines, Alonzo Church (
B.6.7
), a U.S. mathematician based in Princeton,
New Jersey, had defined a formalism of logic and propositions that he called
lambda calculus
(
Fig. 6.6
). Church argued that any “effectively calculable”
problem corresponded to a lambda calculus expression. He had also been
able to use his formalism to show that the problem of deciding whether
one string of symbols could be converted into another string was unsolv-
able, in the sense that there was no lambda expression that could do this.
In this way Church had been able to show that Hilbert's third question, the
Entscheidungsproblem
, was also unsolvable. Although coming at the problem
from very different perspectives, Turing and Church had both proved the
problem's insolvability.
The statement - that anything effectively computable is computable by
a Turing machine - is known as the
Church-Turing thesis
. It is called a the-
sis rather than a theorem because it involves the informal concept of effec-
tive computability. The thesis equates the mathematically precise statement,
“computable by a Turing machine,” with the informal, intuitive idea of a
problem being solvable by some algorithm on any machine whatsoever. It
applies to all computable problems written in any programming language on
any computer!
The Church-Turing thesis is only a thesis but the majority of computer sci-
entists accept its validity because many people besides Church and Turing have
arrived at an equivalent result. At about the same time as Church and Turing's
work, mathematicians Stephen Kleene and Emil Post devised alternative for-
malisms that led to similar notions of computability. Many others have looked
at variants of the simple Turing machine such as machines with multiple tapes
or machines with two-dimensional tapes. None of these machines can solve
problems that cannot be solved by the basic Turing machine.
Y
1
R
0
0
A
A
B
R
L
1
Y
B
HALT
R
1
B
A
0
X
Y
1
0
1
L
START
0
0
A
B
L
X
1
A
B
R
S
S
R
B
A
R
M
M
L
L
M
M
0
1
Y
Y
0
1
R
L
R
R
0
0
X
X
0
1
X
0
0
A
A
B
B
R
L
L
A
B
L
L
S
0
1
S
B
L
A
M
M
B
A
1
0
R
B
A
0
1
X
1
R
0
Fig. 6.5. A representation of a Universal
Turing Machine due to Marvin Minsky.
Fig. 6.6. The “Knights of the Lambda
Calculus,” the unofficial badge of LISP
programmers at MIT.
Search WWH ::
Custom Search