Fork me on GitHub
Math for the people, by the people.

User login

Please help on Turing Machine Problems

Primary tabs

Please help on Turing Machine Problems

Can someone please help me on this problem ?

1.(i ) Consider the task of deciding if any given Turing Machine (TM) will from an initial blank tape ever print a non-blank on the initially scanned square. Assuming the Blank Tape Halting Problem (BTHP) Theorem, show that this task is Turing Impossible.

(ii ) Let us call any square on a tape currently significant if it is currently non-blank, or if it is currently scanned, or if it lies between two squares each currently non-blank or scanned, and consider the task of deciding if any given TM from an initially blank tape will ever have more than 100 currently significant squares on its tape. Show that this task is Turing Possible.


> Can someone please help me on this problem ?

They look like standard exercises in Computation Theory.
Let's try to give a look...

> 1.(i ) Consider the task of deciding if any given Turing
> Machine (TM) will from an initial blank tape ever print a
> non-blank on the initially scanned square. Assuming the
> Blank Tape Halting Problem (BTHP) Theorem, show that this
> task is Turing Impossible.

You must show that, if you were able to solve algorithmically this task, then you would also be able to solve algorithmically the BTHP.
You could do this by modifying a TM that solves your problem into a TM that solves the BTHP.
Alternatively, you could show that, given any TM X, you can always construct a second TM Y such that Y ever prints a non-blank on the initial square starting on the blank tape, if and only if X halts (alternatively, iff X does not halt) starting from the blank tape.

> (ii ) Let us call any square on a tape currently significant
> if it is currently non-blank, or if it is currently scanned,
> or if it lies between two squares each currently non-blank
> or scanned, and consider the task of deciding if any given
> TM from an initially blank tape will ever have more than 100
> currently significant squares on its tape. Show that this
> task is Turing Possible.

I think you could solve this by some kind of enumeration technique, taking into account the number of states and symbols of the TM.

Subscribe to Comments for "Please help on Turing Machine Problems"