turing machine

Page 1

A Turing Machine is not a real machine.

It is an abstract, theoretical concept that represents a computer in its simplest form.

A Turing machine consists of:

A finite set of states A finite alphabet of symbols (a,b,c,1,0,#,!)

An infinite tape with marked off squares

A sensing read/write head that can travel along the tape, one square at a time

Rules for transitioning between states and reading/writing and moving along the tape

On each cycle, the Turing Machine does the following

Reads the value of the current square

Reads the current state

Writes a value to the current square (always writes the something even if it is the same thing)

Moves the tape left or right

Page 2

On each cycle, Turing machine takes two inputs and gives 3 outputs

Inputs: Its current state, The character on the tape

Outputs: A new state, A new character for the tape, A direction to move