|
University of Virginia Computer Science CS150: Computer Science, Fall 2005 |
(none) 24 October 2005 |
What do we need to model computation?
FSM ::= <Alphabet, States, InitialState, HaltingStates, TransitionRules>
Alphabet ::= { Symbol* } A set of symbols for the input.
States ::= { StateName* }
InitialState ::= StateName
Must be one of the states in States.
HaltingStates ::= { StateName* }
Must all be states in States.
TransitionRules ::= { TransitionRule* }
TransitionRule ::= < StateName, Symbol, StateName>
StateName X Symbol → StateName
TM ::= <Alphabet, Tape, TFSM>
Alphabet ::= { Symbol*}
A set of symbols for the tape.
Tape ::= < LeftSide, OneSquare, RightSide >
OneSquare ::= Symbol | #
LeftSide ::= [ Squares* ]
Everything to left of LeftSide is #. RightSide ::= [ Squares* ]
Everything to right of RightSide is #. Squares ::= OneSquare, Squares
Squares ::=
TFSM ::= <States, InitialState, HaltingStates, TransitionRules>
Like a FSM, except the transition rules write to the tape and move the tape head.States ::= { StateName* }
InitialState ::= StateName Must be one of the states in States.
HaltingStates ::= { StateName* } Must all be states in States.
TransitionRules ::= { TransitionRule* }
TransitionRule ::= < StateName, OneSquare, StateName, OneSquare, Direction>
StateName X OneSquare → StateName X OneSquare X Direction
Computing is normally done by writing certain symbols on paper. We may
suppose this paper is divided into squares like a child's arithmetic
book. In elementary arithmetic the two-dimensional character of the
paper is sometimes used. But such a use is always avoidable, and I think
that it will be agreed that the two-dimensional character of paper is no
essential of computation. I assume then that the computation is carried
out on one-dimensional paper, i.e. on a tape divided into
squares. I shall also suppose that the number of symbols which may be
printed is finite. If we were to allow an infinity of symbols, then
there would be symbols differing to an arbitrarily small extent. The
effect of this restriction of the number of symbols is not very
serious. It is always possible to use sequences of symbols in the place
of single symbols. Thus an Arabic numeral such as 17 or 999999999999999 is
normally treated as a single symbol. Similarly in any European language
words are treated as single symbols (Chinese, however, attempts to have
an enumerable infinity of symbols). The differences from our point of
view between the single and compound symbols is that the compound
symbols, if they are too lengthy, cannot be observed at one glance. This
is in accordance with experience. We cannot tell at a glance whether
9999999999999999 and 999999999999999 are the same.
The behaviour of the computer at any moment is determined by the symbols which he is observing. and his “state of mind” at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite. The reasons for this are of the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be “arbitrarily close” and will be confused. Again, the restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape. ...
We may now construct a machine to do the work of this computer. To each state of mind of the computer corresponds an “m-configuration” of the machine. The machine scans B squares corresponding to the B squares observed by the computer. In any move the machine can change a symbol on a scanned square or can change anyone of the scanned squares to another square distant not more than L squares from one of the other scanned squares. The move which is done, and the succeeding configuration, are determined by the scanned symbol and the m-configuration....
Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, 1936.
|
CS 150: Computer Science University of Virginia |
evans@virginia.edu Using these Materials |