Question

3. [10 marks] This question investigates variants of our standard TM model from class (a) [5 marks] Consider a TM which, if it ever attempts to move the head left while on the first cell, self destructs, ie, a "self-destructing TM”. Show that a self-destructing TM can simulate a standard TM

Answer 1

An attempt to move head left from the first cell cause abnormal termination. To avoid this problem end-of-tape marker can be use in the first tape cell. This symbol (as marker) is not used elsewhere in the tape.

Consider the example of Turing machine which can accept the language {a^ n b^ n c^ n : n ≥ 0}.

So the tape looks something like this: αxxaayybbzzcc…..

The α is the left end marker, mark by special symbol α that cannot be erased. So to prevent falling off the head left from the first cell. Finally the Turing machine checks as the standard turing machine.