2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is the tape infinite on the left and on the right? $\endgroup$ – Taroccoesbrocco Aug 3 at 15:53
  • $\begingroup$ @Taroccoesbrocco: the tape is one-way infinite (thus there exists the leftmost cell) $\endgroup$ – lyrically wicked Aug 3 at 15:56
  • $\begingroup$ If your are in the leftmost cell, how can the transition function dictate the machine to move the head to the left? If it happens it means that your Turing Machine is not well defined. $\endgroup$ – Ruggiero Rilievi Aug 3 at 16:56
  • 1
    $\begingroup$ @RuggieroRilievi: “If your are in the leftmost cell, how can the transition function dictate the machine to move the head to the left?” — such programs are definitely possible. They are absolutely valid programs in the mathematical sense. $\endgroup$ – lyrically wicked Aug 3 at 17:42
  • $\begingroup$ Why not just ignore an instruction that would cause the head to fall off the tape? $\endgroup$ – Matt Samuel Aug 3 at 20:29
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

So, as I understand your concern is regarding the computational model in this paper. Now based on the first quotation in your question (this quote is from mathoverflow version of your question, where you quoted a sentence from this paper):

Computation ceases only when the halt state is explicitly obtained, and in this case, the output is whatever is written on the output tape. (If the head falls off the tape, no output is given.)

To be specific, let's assuming we are just considering functions from $\mathbb{N}$ to $\mathbb{N}$. As far as I can understand the above quote, the intended meaning is that if on some input $x \in \mathbb{N}$ while during the course of computation the heads falls off the tape then $f(x)$ is supposed to be undefined. That is, $f$ will be considered partial on the input $x$ (same as never halting).

Below I will assume that we have a simple way to relate the output with any possible configuration on output tape. For example, one way is to take the number of consecutive 1's (starting from cell at 0-position) that occur on the output tape as output. And if the tape is all 1's then take the output to be 0.

Now call the computational model with the above convention as $C_1$. Now one way I interpret your question (this might not be best way) is that what if we changed the convention and declared that if head falls off the tape for some input then we declare the output to be whatever was on the output tape at that time. Would the resulting computational model (say $C_2$) calculate the same collection of functions (from $\mathbb{N}$ to $\mathbb{N}$) as $C_1$? Call the set of functions ($\mathbb{N}$ to $\mathbb{N}$) computed by $C_1$,$C_2$ as $A_1$,$A_2$ respectively. The question is whether $A_1=A_2$?

There are two directions to the equality: $A_1 \supseteq A_2$ and $A_2 \supseteq A_1$. Let's focus on the first inequality. We essentially want to simulate the model $C_2$ within $C_1$. Now consider a specific machine in the model $C_2$. If we want to simulate the same machine in $C_1$, we want to have a (general) way of "knowing" when the head falls off the tape. Because in that case we want to output whatever is on output tape (instead of returning an undefined value).

The first thing is that since there are three tapes, I will write something like $[0,1,0]$ to denote a given (composite) "cell" (which is composed of three individual cells). Now when the program is start state we first move to the right (say 5 times) and print $[1,1,1]$ the same number of times (so the first five cells will be all $[1,1,1]$) ---- but this is after re-adjusting the input given to us. Now the main trick is that (after the first five cells), in our simulation, to represent a cell such as $[1,0,1]$ (in the original program given in $C_2$) we use two consecutive cells. We represent $[1,0,1]$ as two cells (placed side-by-side): $[0,0,0]$,$[1,0,1]$. The general idea is that any cell such as $[a,b,c]$ (in original program of $C_2$) will be represented (in our simulation via $C_1$) by two adjacent cells that will be: $[0,0,0]$,$[a,b,c]$.

Now on limits since our machine moves to a special "limit state" with the head being set to the left-most position. So whenever we are in limit-state, we again move five times to the right printing $[1,1,1]$. In the original program (of $C_2$) whenever it has a transition from one state to other, we need to decompose it in our simulation. If the original transition was say $([1,0,1],[1,0,0],R)$ (from $s_{10}$ to $s_{11}$ say), we need to decompose it into further states/transitions. The point is that $[1,0,1]$ is represented as $[0,0,0]$,$[1,0,1]$ (in our simulation). So if our pointer was on $[0,0,0]$ we first move one step to the right unconditionally (with intermediate states). After that we will have a transition $([1,0,1],[1,0,0],R)$ (and that transition will lead to a new state analogous to $s_{11}$ in our simulation). This way while the original program (in $C_2$) changed a cell $[1,0,1]$ to $[1,0,0]$. In our simulation (using program $C_1$), we are changing the "adjacent cells" $[0,0,0]$,$[1,0,1]$ TO $[0,0,0]$,$[1,0,0]$.

Sorry it got a bit long-winded. But the real point is that after the first five consecutive cells $[1,1,1]$, in our simulation each of the original cells of the form $[a,b,c]$ (with $a,b,c \in \{0,1\}$) in the program $C_1$ are now represented by "two adjacent cells" of the form $[0,0,0]$,$[a,b,c]$. If you consider carefully the "head falling off the tape" now will be indicated by occurrence of two consecutive cells of the form $[1,1,1]$,$[1,1,1]$ (when we are simulating a transition that moves the head left).

So now in our simulation of the program of $C_2$ (via $C_1$) whenever we detect the "head falling off the tape", we halt immediately (after changing the output to desired form). Observe that there is a little that needs to be changed when we want to show $A_2 \supseteq A_1$ (except for the very last part, everything remains same).

$\endgroup$
  • $\begingroup$ My point is that if you are considering the collection of all function (from $\mathbb{N}$ to $\mathbb{N}$), whatever convention you assume it wouldn't matter. For example, in you program above you may assume: (1) the program loops (2) the program goes to the "special halt state" (with output being whatever was on output tape). It wouldn't change the class of functions computed no matter which convention you took. $\endgroup$ – SSequence Aug 19 at 9:51
  • $\begingroup$ Yes, I think that the "special halt state" (a dedicated ERROR-HALT state) is a suitable solution. $\endgroup$ – lyrically wicked Aug 19 at 9:54
  • $\begingroup$ @lyricallywicked Yes, in these kind of circumstances (where nothing essential is changed) it is reasonable to take whatever convention one is comfortable with. $\endgroup$ – SSequence Aug 19 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.