[Math] What happens if the head of an Infinite Time Turing Machine is at the leftmost cell and the program dictates to move the head to the left

logicturing-machines

What happens when the head of an Infinite Time Turing Machine is at the first (leftmost) cell and the current instruction dictates the machine to move the head to the left? I have not seen any explicit rule for such situation in the original paper. I have seen a solution that extends the alphabet by one additional symbol, but I am interested in a solution that does not extend the two-symbol (one blank symbol and one non-blank symbol) alphabet.

The following excerpts are taken from the paper “The halting problem is decidable on a set of
asymptotic probability one”:

If the machine attempts to move left from the left-most cell, then the head falls off the tape and all computation ceases.
[…]
If the head falls off the tape, then the computation cannot reach the halt state
[…]
computations for which the head falls off the tape are not counted as halting
[…]
The reader will have already observed, of course, that our argument does not work with Turing machines using doubly-infinite tapes, another common model, for which there is no possibility that the head falls off the tape. And neither does it work with the one-way infinite tape models that allow computation somehow to continue after attempting to move left from the left-most cell.

So I see two possible solutions:

  1. Define one additional HALTFALL state which occurs automatically when the head falls off the tape and all computation ceases;
  2. Allow computation to continue after attempting to move left from the left-most cell. But how can this be done?

I still do not know what solution is more suitable for Infinite Time Turing Machines.

Best Answer

You have proposed two good alternatives for resolving the question. Now you should ask:

  1. Is there any difference between these two?
  2. If there is a difference, do both solutions still validate the main theorems about infinite-time Turing machines (u-t-m and s-m-n theorems in particular)?

It's worthwhile thinking about these by yourself, as that will deepen the undersanding of Turing machines.

Regarding equivalence of the two solutions, as fas as I can see, we can transform a fall-of-the-tape machine to just-do-not-move-left-of-first-cell machine by placing a special marker at the begining of the tape (and moving the rest of the input slightly to the right, which may take $\omega$ steps for an infinite-time Turing machine). For the other direction, once again we can place a marker at the extreme left and go on a special state if we ever attempt to move left of that marker.

So all in all, there isn't a lot of difference and it doesn't matter what you do.

Related Question