next up previous contents
Next: Two-way infinite tape Up: TM's continued Previous: TM's continued

instantaneous description of Turing machine

All symbols to left of head, State of machine, symbol head is scanning and all symbols to right of head, i.e.

(X_1 X_2 \ldots X_{i-1} q X_{i} \ldots X_{n}).\end{displaymath}

Example of Turing machine accepting a string with equal numbers of zeros and ones - this can't be done with FA, as was previous shown.

Programming Turing machine can be done entirely in finite state logic, but can also be done with information on tape.

Finite state logic can also be used to store information, by including tape symbol dependent states.