University of Virginia Computer ScienceCS150: Computer Science, Fall 2005 |
(none)24 October 2005 |

- (Ideally as soon as possible) Read GEB,
*Aria with Diverse Variations*and Chapter 13. This chapter proves that the halting problem is not decidable, and introduces the Church-Turing Thesis (which we will explore more in later classes). You will not be assigned to read Chapter XIV, but it goes into more depth on Gödel's proof and is recommended. - Monday, 31 October: Problem Set 6

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 inStates.

HaltingStates::= {StateName^{*}}

Must all be states inStates.

TransitionRules::= {TransitionRule^{*}}

TransitionRule::= <StateName,Symbol,StateName>

StateNameXSymbol→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::=StateNameMust be one of the states inStates.

HaltingStates::= {StateName^{*}} Must all be states inStates.

TransitionRules::= {TransitionRule^{*}}

TransitionRule::= <StateName,OneSquare,StateName,OneSquare,Direction>

StateNameXOneSquare→StateNameXOneSquareXDirection

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 ScienceUniversity of Virginia |
evans@cs.virginia.eduUsing these Materials |