|
version
history
HOW TO CITE
THIS ENTRY
|
Stanford Encyclopedia of Philosophy
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z
|
This document uses HTML 4/Unicode to display special characters. Older
browsers and/or operating systems may not display these characters correctly.
|
|
last substantive
content change
|
Turing Machine
A Turing machine is an abstract representation of a computing device.
It consists of a read/write head that scans a (possibly infinite)
one-dimensional (bi-directional) tape divided into squares, each of
which is inscribed with a 0 or 1. Computation begins with the
machine, in a given "state", scanning a square. It erases what it
finds there, prints a 0 or 1, moves to an adjacent square, and goes
into a new state. This behavior is completely determined by three
parameters: (1) the state the machine is in, (2) the number on the
square it is scanning, and (3) a table of instructions. The table of
instructions specifies, for each state and binary input, what the
machine should write, which direction it should move in, and which
state it should go into. (E.g., "If in State 1 scanning a 0: print 1,
move left, and go into State 3".) The table can list only finitely
many states, each of which becomes implicitly defined by the role it
plays in the table of instructions. These states are often referred
to as the "functional states" of the machine.
A Turing machine, therefore, is more like a computer program
(software) than a computer (hardware). Any given Turing machine can
be realized or implemented on an infinite number of different physical
computing devices. Computer scientists and logicians have shown that
if conventional digital computers are considered in isolation from
random external inputs (such as a bit stream generated by radioactive
decay), then given enough time and tape, Turing machines can compute
any function that any conventional digital computer can compute. (We
won't consider whether Turing machines and modern digital computers
remain equivalent when both are given external inputs, since that
would require us to change the definition of a Turing machine.) Also,
a ‘probabilistic automaton’ can be defined as a Turing
machine in which the transition from input and state to output and
state takes place with a certain probability (E.g. "If in State 1
scanning a 0: (a) there is a 60% probability that the machine will
print 1, move left, and go into State 3, and (b) there is a 40%
probability that the machine will print 0, move left, and go into
State 2".)
Turing machines were first proposed by Alan Turing, in an attempt to
give a mathematically precise definition of "algorithm" or "mechanical
procedure". Early work by Turing and Alonzo Church spawned the branch of
mathematical logic now known as recursive function theory.
The concept of a Turing machine has played an important role in the
recent philosophy of mind. The suggestion has been made that mental
states just are functional states of a probabilistic automaton, in
which binary inputs and outputs have been replaced by sensory inputs
and motor outputs. This idea underlies the theory of mind known as
"machine functionalism".
- Turing, A., "On Computable Numbers, With an Application to the
Entscheidungsproblem", Proceedings of the London Mathematical
Soceity, Series 2, Volume 42, 1936; reprinted in M. David (ed.),
The Undecidable, Hewlett, NY: Raven Press, 1965
- Boolos, G. and Jeffrey, R., Computability and Logic, 2nd
ed., Cambridge: Cambridge University Press, 1980.
- Putnam, H., "The Nature of Mental States", in Mind, Language
and Reality: Philosophical Papers II, Cambridge: Cambridge
University Press, 1975
artificial intelligence |
Church-Turing Thesis |
functionalism |
Turing, Alan
Acknowledgement
The Editors would like to thank Stuart Shieber for pointing out that
Turing machines need not have infinite, two-dimensional tapes, but
that infinite, one-dimensional and bidirectional tapes suffice. We'd
also like to thank Jef Raskin and Joshua Stern for helpful comments
about the equivalence of Turing machines and conventional digital
computers.
Copyright © 1995, 2003
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z
Stanford Encyclopedia of Philosophy