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
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) two-dimensional 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
Turing machines -- given enough time and tape -- can compute any
function that any conventional digital computers can compute. 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
Copyright © 1995, 2000 by
The Editors
editors@plato.stanford.edu
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
Table of Contents
First published: September 14, 1995
Content last modified: February 10, 2000