Introduction to Automata Theory, Languages, and Computation |

- Never halts unless we explicitly want it to, and
- Halts whenever it prints
`hello, world.`

For (1), we can add a loop such as `while(1){x=x;}` to the end of
`main`, and also at any point where `main` returns.
That change catches the normal ways a program can halt, although it
doesn't address the problem of a program that halts because some
exception such as division by 0 or an attempt to read an unavailable
device.
Technically, we'd have to replace all of the exception handlers in the
run-time environment to cause a loop whenever an exception occurred.

For (2), we modify *P* to record in an array the first 12
characters printed.
If we find that they are `hello, world.`, we halt by going to the
end of `main` (past the point where the while-loop has been
installed).

*[q0]00 |- X[q1]0 |- X0[q1]*

The TM halts at the above ID.

state | 0 | 1 | B | X | Y |
---|---|---|---|---|---|

q0 | (q2,X,R) | (q1,X,R) | (qf,B,R) | - | (q0,Y,R) |

q1 | (q3,Y,L) | (q1,1,R) | - | - | (q1,Y,R) |

q2 | (q2,0,R) | (q3,Y,L) | - | - | (q2,Y,R) |

q3 | (q3,0,L) | (q3,1,L) | - | (q0,X,R) | (q3,Y,L) |

qf | - | - | - | - | - |

In explanation, the TM makes repeated excursions back and forth along
the tape.
The symbols *X* and *Y* are used to replace 0's and 1's that
have been cancelled one against another.
The difference is that an *X* guarantees that there are no
unmatched 0's and 1's to its left (so the head never moves left of an
*X*), while a *Y* may have 0's or 1's to its left.

Initially in state *q0*, the TM picks up a 0 or 1, remembering it
in its state (*q1* = found a 1; *q2* = found a 0), and cancels
what it found with an *X*.
As an exception, if the TM sees the blank in state *q0*, then all
0's and 1's have matched, so the input is accepted by going to state
*qf*.

In state *q1*, the TM moves right, looking for a 0.
If it finds it, the 0 is replaced by *Y*, and the TM enters state
*q3* to move left an look for an *X*.
Similarly, state *q2* looks for a 1 to match against a 0.

In state *q3*, the TM moves left until it finds the rightmost
*X*.
At that point, it enters state *q0* again, moving right over
*Y*'s until it finds a 0, 1, or blank, and the cycle begins again.

For part (a), given an input *[x,y]*
use a second track to simulate the TM for *f* on the input
*x*.
When the TM halts, compare what it has written with *y*, to see if
*y* is indeed *f(x)*.
Accept if so.

For part (b), given *x* on the tape, we need to simulate the TM
*M* that recognizes the graph of *f*.
However, since this TM may not halt on some inputs, we cannot simply try
all *[x,i}* to see which value of *i* leads to acceptance by
*M*.
The reason is that, should we work on some value of *i* for which
*M* does not halt, we'll never advance to the correct value of
*f(x)*.
Rather, we consider, for various combinations of *i* and *j*,
whether *M* accepts *[x,i]* in *j* steps.
If we consider *(i,j)* pairs in order of their sum (i.e., (0,1),
(1,0), (0,2), (1,1), (2,0), (0,3),...) then eventually we shall simulate
*M* on *[x,f(x)]* for a sufficient number of steps that
*M* reaches acceptance.
We need only wait until we consider pairs whose sum is *f(x)* plus
however many steps it takes *M* to accept *[x,f(x)]*.
In this manner, we can discover what *f(x)* is, write it on the
tape of the TM that we have designed to compute *f(x)*, and halt.

Now let us consider what happens if *f* is not defined for some
arguments.
Part (b) does not change, although the constructed TM will fail to
discover *f(x)* and thus will continue searching forever.
For part (a), if we are given *[x,y]*, and *f* is
not defined on *x*, then the TM for *f* will never halt on
*x*.
However, there is nothing wrong with that.
Since *f(x)* is undefined, surely *y* is not *f(x)*.
Thus, we do not want the TM for the graph of *f* to accept
*[x,y]* anyway.

state | 0 | 1 | B |
---|---|---|---|

q1 | (q2,0,R) | - | - |

q2 | (q2,0,R) | (q3,1,R) | (q3,B,R) |

q3 | (q4,0,L) | (q4,1,L) | (q4,B,L) |

Now, we can use this subroutine in a TM that starts in state *q0*.
If this TM ever sees the blank, it accepts in state *qf*.
However, whenever it is in state *q0*, it knows only that it has
not seen a 1 immediately to its right.
If it is scanning a 0, it must check (in state *q5*) that it does
not have a blank immediately to its right; if it does, it accepts.
If it sees 0 in state *q5*, it comes back to the previous 0 and
calls the subroutine to skip to the next non-0.
If it sees 1 in state *q5*, then it has seen 01, and uses state
*q6* to check that it doesn't have another 1 to the right.

In addition, the TM in state *q4* (the final state of the
subroutine), accepts if it has reached a blank, and if it has reached a
1 enters state *q6* to make sure there is a 0 or blank following.
Note that states *q4* and *q5* are really the same, except
that in *q4* we are certain we are not scanning a 0.
They could be combined into one state.
Notice also that the subroutine is not a perfect match for what is
needed, and there is some unnecessary jumping back and forth on the tape.
Here is the remainder of the transition table.

state | 0 | 1 | B |
---|---|---|---|

q0 | (q5,0,R) | (q6,1,R) | (qf,B,R) |

q5 | (q1,0,L) | (q6,1,R) | (qf,B,R) |

q6 | (q0,0,R) | - | (qf,B,R) |

q4 | - | (q6,1,R) | (qf,B,R) |

Once the copying is done, retract the head of tape 2 to the left end of
the 100 symbols.
Then, continue moving right on tape 1, and at each cell guess either to
continue moving right or to guess that the second copy of *x*
begins.
In the latter case, compare the next 100 symbols on tape 1 with the 100
symbols on tape 2.
If they all match, then move right on tape 1 and accept as soon as a
blank is seen.

Part (b), doing the same thing deterministically, is trickier, since we
might start off in the wrong direction and travel forever, never seeing
the $.
Thus, we have to oscillate, using left and right endmarkers *X* and
*Y*, respectively, to mark how far we have traveled on a second
track.
Start moving one cell left and leave the *X*.
Then, move two cells right and leave the *Y*.
Repeatedly move left to the *X*, move the *X* one more cell
left, go right to the *Y*, move it once cell right, and repeat.

Eventually, we shall see the $. At this time, we can move left or right to the other endmarker, erase it, move back to the end where the $ was found, erase the other endmarker, and wind up at the $.