## Primary tabs

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.

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

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