For example, can a TM preform this simple task.

Starting from an initial square, print a non-blank on the 10th square strictly to the right or left?

Thanks

Printable View

- April 15th 2011, 11:13 PMikurwae89Can a Turing Machine(TM) know what square its at ?
For example, can a TM preform this simple task.

Starting from an initial square, print a non-blank on the 10th square strictly to the right or left?

Thanks - April 17th 2011, 10:41 AMemakarov
A TM can keep track of its head position up to a finite limit through its internal state. For example, a machine can have 100 states (plus some). If it moves to the right, it changes from state n to state n + 1, and if it moves to the left, it changes from n to n - 1. However, if it moves beyond square 100, it can no longer keep track of its position.

So yes, a machine can easily print a non-blank character on the 10th square to the right of the initial square.

This sounds a lot like a finite automaton, but there is still a big difference. Yes, when the size of the input is not bounded from above, the machine eventually can't "know" precisely where it is located. However, the combination of the facts that, in addition to the internal state, a TM is guided by the current tape square, that a TM can write on the tape and that the tape is infinite makes it possible for TMs to perform all possible computations.