Turing Machines - 1

In the way it is usually defined a Turing machine has an infinite tape for storage. This storage tape serves also as the input device and the output device.

Even though the tape is infinite it is to be noted that the definition specifically mentions that all except a finite number of squares are blank. This means that a TM is actually dealing with a finite string. We could have a finite string with two end of the line symbols and arrange matters so that if the reading head happens to see one of them it simply moves it one square away. See the Book for a detailed definition along these lines.

But if a TM actually deals with finite but arbitrarily long strings, just like finite automata, then how is it that a TM can be universal? The reason is the ability of the head of the TM to move both forward and back and change the symbols it encounters.

In the next post I will attempt a simple argument that shows that a TM is "naturally and obviously" universal.