version history
|
Stanford Encyclopedia of PhilosophyA | 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 XHTML/Unicode to
format the display. If you think special symbols are not displaying
correctly, see our guide Displaying
Special Characters. | |
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.
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