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