Please help on Turing Machine Problems

## Primary tabs

# Please help on Turing Machine Problems

Submitted by Jess123 on Mon, 04/07/2008 - 13:06

Forums:

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.

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Re: Please help on Turing Machine Problems

> 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.