If the tape initially contains some 1s, then there is slightly more work to do. If we don't know how many 1s there are, nor where they are, then life is difficult [our TM might be apparently in a loop drifting down the tape, but 1000 years hence it encounters a 1 and its behaviour changes ...], so we assume that the emulator can find all the 1s. [If it knows how many, then it can search for them by scanning left for so long, then right a bit further, then left a bit further still, etc., until they've all been found.] Suppose they and the initial head position are within a length L of tape. Extend this by N squares at each end. If the TM ever goes outside this region, then within the last N ticks it has either written a 1 or else has repeated a state. If it has not written a 1, then it has not read one either, and therefore it is in a loop reading blanks and going further away from the `interesting' region. If it does not stray outside this region, then within N(L + 2N) ticks it must either change the tape or repeat a state and a position on the tape. If it repeats state and position without changing the tape, then it is again in a loop. If it changes the tape, then either it writes a 1 or it changes an existing 1 to a 0; but it can do the latter no more than L times in succession. We conclude that the TM will write a 1 within the first LN(L + 2N) ticks or not at all. [Note: It doesn't matter whether or not we regard reading a 1 and writing it back without change as writing a 1.]
This result can be generalised slightly to show that we can decide whether or not a TM ever overwrites a symbol by one later in [some] alphabetical order [such as ASCII], provided that the `blank' symbol, here 0, is at the start of the alphabet. But note that the proof of the `printing' problem involved the use of a `new' symbol -- in other words, to `solve' the halting problem for a binary TM, we would need to show that a ternary TM printed a particular symbol. Our present result merely shows that the halting problem for unary TMs [completely blank, featureless tape!] is solvable -- big deal! In similar vein, you might like to contemplate that the emulation of LN(L + 2N) ticks may take an arbitrarily long time, even though the emulator is [presumably] fixed -- why does this not contradict that stuff about computable functions and busy beavers?
increment (a) // make sure it's non-zero L1: decrement (a) if (a != 0) goto L1(ii) The simplest way to do this sort of exercise is to write suitable code in simplified C [or whatever], then keep on simplifying it. For example,
b = a c = a a = 0 while (b != 0) decrement (b) a += cIf we first check that a is non-zero, then we don't need to test b at the top of the loop, and other things are easier, so we get
if (a != 0)
b = a, c = a, a = 0
{ decrement (b), a += c } while (b != 0)
The test on a is really backwards, as we want to
`skip' if a is zero;
so we end up with
if (a != 0) goto L1 increment (b) if (b != 0) goto L2 // `unconditional' jump L3: decrement (b) // zero b L1: if (b != 0) goto L3 increment (c) // zero c L4: decrement (c) if (c != 0) goto L4 increment (t) // zero temp vble L5: decrement (t) if (t != 0) goto L5 L6: decrement (a) // copy a to b and c, zero a increment (b) increment (c) if (a != 0) goto L6 L7: decrement (b) L8: increment (a) // a += c, t = c, c = 0 increment (t) decrement (c) if (c != 0) goto L8 L9: increment (c) // restore c decrement (t) if (t != 0) goto L9 if (b != 0) goto L7 L2:(iii) No detailed solution supplied! The basic idea is something like
m = a while (m != 0) decrement (m) if (REM (a, m) != 0) goto out out: a = 1 if (m == 1) decrement (a)where REM computes the remainder when a is divided by m [left as an `easy' exercise!].