3
$\begingroup$

Consider a transfinite Turing Machine model, allowing ordinal-length tape and time, and a number of states of arbitrary cardinality.

Is there an algorithm P with at most $\aleph_{0}$ states, such that P halt after $\omega_{1}$ steps on the empty input?

$\endgroup$
  • $\begingroup$ I don't understand what you mean by transfinite Turing machine. Suppose I have a tape of length $2 \omega$ and the program says to (over)write $2n$ $\alpha$s then to overwrite these with $2n+1$ $\beta$s for $n \in \mathbb{N}$. Does the cursor ever reach the second half of the tape? If not, what is the point? If so, what is on the first half of the tape when the cursor first reaches the second half? $\endgroup$ – Douglas Zare Aug 1 '17 at 16:02
  • $\begingroup$ @DouglasZare there is a standard model of ordinal Turing machines. At a limit stage, the head position is set into the liminf of the earlier positions; each cell is updated with liminf, and the program state is the liminf. For example, see math.uni-bonn.de/people/koepke/Preprints/… and related. (Separately, I think you mean $\omega\cdot 2$ rather than $2\omega$; also, usually each cell is $0$ or $1$ or a finite alphabet.) $\endgroup$ – Joel David Hamkins Aug 2 '17 at 22:30
  • $\begingroup$ @Joel David Hamkins: Thanks for the explanation and correction. So, there is no longer any symmetry in a finite alphabet? $\endgroup$ – Douglas Zare Aug 3 '17 at 1:12
  • $\begingroup$ Yes, the symbols are linearly ordered and this order is used to define the configuration of the machine at limit stages. But there is symmetry in that one can detect the kind of limit and simulate another order. For example, it wouldn't have mattered whether you use limsup or liminf, since you can detect and simulate the other kind. So the class of computable functions is not sensitive to this choice. $\endgroup$ – Joel David Hamkins Aug 3 '17 at 1:26
6
$\begingroup$

The answer is no, there is no such program.

Let me say, first, that allowing countably infinitely many states into the program is basically equivalent to having a finite program with a real parameter, since one can have a master control program that consults the real parameter to see what it should do next; this would align things a little closer with how the theory is usually undertaken. But it is of no consequence, and I can go along with your infinite program.

Suppose that $p$ is one of your programs, and we run it on an ordinal-length empty tape, and suppose that it halts at time $\omega_1$. Consider the relativized constructible universe $L[p]$, and observe that the operation of the program $p$ is absolute to this universe $L[p]$. Indeed, if $\theta>\omega_1$, then the operation of the machine is absolute to $L_\theta[p]$, which will therefore observe that the program halts at stage $\omega_1$. By the Löwenheim-Skolem theorem and condensation, there is a countable ordinal $\gamma$ with an elementary embedding $L_\gamma[p]\precsim L_\theta[p]$. It follows that $L_\gamma[p]$ also observes that $p$ halts at the ordinal $\omega_1^{L_\gamma[p]}$, which is a countable ordinal less than $\gamma$. But the operation of the machine at stages below $\gamma$ is absolute to $L_\gamma[p]$, and so the program must really halt at that countable stage, contradicting out assumption.

The argument shows that every such program, even allowing countably infinitely many states, must halt at a countable stage, if it halts at all.

Another way to see this is to point out that the halting nature of a program is a $\Sigma_1$ expressible fact about the program, and so if this $\Sigma_1$ statement about $p$ is true, then it will become true by the first $\Sigma_1(p)$ stable ordinal, which is countable.

Meanwhile, the very first theorem of my paper

shows that in the case of infinite time Turing machines, which allow a tape of length $\omega$ rather than Ord as in your question, every halting computation must halt at a countable stage. Indeed, every computation either halts or strongly repeats at a countable stage.

$\endgroup$
  • $\begingroup$ Doesn't this argument depend on a certain "simplicity" in the description of p? Is it not possible that p is complex enough that L of p contains enough ordinals to render L-S and condensation ineffective in shortening the running time? I am hoping you can make this argument even more explicit to me , who has almost no experience with transfinite Turing machines. (In particular, can I understand p like a machine with a transfinite oracle?) Gerhard "Amazon Sells No Transfinite Raspberry-Pis" Paseman, 2017.07.31. $\endgroup$ – Gerhard Paseman Aug 1 '17 at 2:55
  • 1
    $\begingroup$ Well, I assumed that $p$ is a Turing machine program, which does have a simple description in how it is to operate. If that is not what is meant, then one would have to specify the computational model more fully. But the argument I gave is actually quite general, and will still apply to other models, provided that the operation of the machine can be described in set theory and is absolute to those models of set theory. It would be very strange for a model of computability to not be absoluten, since it would mean the operation of the machine would depend on the universe in which it is run. $\endgroup$ – Joel David Hamkins Aug 1 '17 at 2:59
  • $\begingroup$ As for the operation of transfinite Turing machines, Gerhard, probably my article linked in my answer could serve as a gentle introduction. Later work generalized this to tapes of length Ord, as in the question, but it is easier to start with the normal hardware. I think we were both in Berkeley at the time when the ITTM theory was first getting started, in the early 1990s. Do you remember Jeff Kidder and I sharing an office? And Andy Lewis was also there, but didn't get involved until later. $\endgroup$ – Joel David Hamkins Aug 1 '17 at 3:10

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.