# What set theoretical questions could never be answered by Turing machines of arbitrary cardinality?

Let us assume that there are Turing machines of arbitrary cardinality, by that I mean they can have input tapes of any arbitrarily high cardinality and compute for a number of steps also of arbitrarily high cardinality. Those machines are, in principle, much more powerful than Hamkins infinite time Turing machines. Basically what I mean is, assume we are not limited by any kind of finiteness so we can construct sets and verify their properties without any cardinal limitation. Assuming we are gods that can watch the results of those computations, it is still not clear to me if questions such as the existence of $0^\#$ (or $V=L$) would be answered by such a machine or if those questions are for ever undecidable (Gödel?) and so you will be always able to define two consistent theories, one in which V=L and one in which $V\not =L$). In the latter case, what makes our hypothetical machine unable to answer the question? (I mean, what makes a property not being able to be tested as either true or false if you are allowed an arbitrarily high infinite number of cells and time steps?)

Edit by P.W.: Without rewriting the question, I believe the following is something like the intention of the original question: allowing a Turing Machine to act transfinitely (as the Hamkins-Kidder Infinite Time Turing machine does) but supplying it with an On-length tape (rather than an omega order-type length as they do) tape, and making some sensible assumptions about its behaviour at limit stages, can such a machine 'decide' or otherwise settle questions, such as $V=L$ or whether $0^\#$ exists? Or, alternatively what can such machines 'compute' or write on their tape(s)? This does have a clear answer.

UPDATE by OP: Thanks to all for your answers and comments. With the risk of going into the ridicule, let me assume that our hypothetical machine (do not call it Turing as it could be misleading), however it works, should be able to build all finite sets of an arbitrary cardinal $\kappa$ and decide if it is a Ramsey cardinal (R)? (Am I asking too much of such a machine?). If so, the statement V=L might be "(super-)undecidable" (that is, if a Ramsey cardinal does not exist the machine never halts), but it must be either true or false. Thus, assuming we are gods (and so we have oracles for our machines' halting problems), we could say that V=L is either true or false, not just an arbitrary axiom (I know that in such a case we can always have models where V=L is true (when $\kappa$=lowest R), but that is not what I mean).

PS: I know it most likely doesn't matter the original motivation in this forum, but the question is related to an argument about Max Tegmark's mathematical universe hypothesis (which to me should be the same as Joel Hamkins multiverse "if ..."), and if he is too restrictive in assuming only Gödel computable mathematical structures.

• You'll have to define more precisely what you mean by "compute" and "construct." Mar 10 '14 at 4:52
• Let us say we follow the Von Newman rules to construct V (which I also mean equivalently by compute) Mar 10 '14 at 4:53
• If that's what you mean, then the answer is trivial. You're constructing V and things are just either true or false there. Mar 10 '14 at 4:56
• Noah, what do you mean "write" a set? L is uncountable. It has more than we can "write." Mar 10 '14 at 5:04
• Thanks Noah, I see better where my mistake lie. I'll go back to the books to fully understand why "most" of the sets will be nonconstructible, so these issues are still a weak point of mine. Mar 12 '14 at 22:15

Peter Koepke and his numerous collaborators have studied the ordinal-length tape version of infinite time Turing machines, where one has a tape stretching the length of the ordinals, and one imagines that the device follows deterministic local rules for working on the tape, reaching the higher levels of the tape in transfinite time. The head position of the tape is determined by the liminf of the head positions as it is in the liminf state, and this idea turns out to be really efficient at placing the head just where you would want it in many applications. Much of this theory is now worked out in detail, and there is a considerable literature on the topic. For example, you might look at:

The fundamental lesson that Koepke emphasizes is a transfinite version of the Church-Turing thesis. Namely, most of the natural ordinal-computability concepts lead to the idea that a set of ordinals is computable from ordinal parameters if and only if it is an element of the constructible universe. This same conclusion has now been verified for many different concepts of ordinal computability.

In this sense, then, and returning to your question, these computations can not discover anything except what is in the constructible universe $L$.

Meanwhile, there are other senses in which the devices can compute more, if you give them additional (non-ordinal) input. For example, if $V\neq L$, then there will be functions from the reals to the reals that are computable by the devices, but which are not in $L$. And so one wants to refine the conclusion with the idea of relative constructibility.

• How does such a machine compute a nonconstrucible real? I would imagine that the operation of the machine is absolute for inner models. Mar 10 '14 at 21:00
• It doesn't compute a non constructible real; I was considering the case where we give such a real as input. Mar 10 '14 at 21:25
• Do these things form realizability models, i.e., do they have the $utm$ and $smn$ theorems? They ought to, and if so, I wonder what crazy sort of intuitionistic logic they support. (For instance, infinite-time TM realize an embedding of $\mathbb{N}^{\mathbb{N}}$ into $\mathbb{N}$.) Mar 11 '14 at 5:46
• @andrej There is an snm theorem and a utm theorem, also (if the latter means universal Turing machine?). The link below shows this for the ITTM model (and surveys other results about this construction). About the crazy intuitionistic logic they support: I could not possibly comment.[Google](maths.bris.ac.uk/~mapdw/basics4.2.pdf Characteristics of discrete transfinite Turing machine models: halting times, stabilization times, and Normal Form Theorems in Theoretical Computer Science, vol. 410, Jan. 2009, 426-442 Mar 11 '14 at 7:17
• @PhilipWelch Thanks that's a very useful link to have. I knew about ITTM, I was wondering if other kinds of machines, such as those described in Joel's answer, have similar properties. I would expect the answer to be positive. Mar 11 '14 at 9:35

I should have answered the question much like Joel's - if it had not been on hold! I should have added though that Barnaby Dawson should be credited, independently and perhaps slightly earlier than Peter Koepke, with the idea of running Turing machines along On-length tapes. He formulated a method of writing characteristic functions of sets as 0,1 streams on an output tape. He formulated the "Axiom of Computability" that all sets are outputs on a tape of such a machine. He moreover noticed that a program forever producing sets coding reals say would act in a certain pattern of repetition, and if produced in an infinitely long computation could be produced in one of countable length (in other words the Continuum Hypothesis holds for "Computable Sets"). The global wellordering of such sets is trivial - so to cut the story short what was constructed were the constructible sets of Goedel's $L$.

(This was all written out a few years later in his - unpublished - PhD thesis.)

One point in answer to the original question, is that the construction of any such machine, whether Turing Machines on long tapes, or ordinal register machines working on ordinals, is that they could never in any sense decide'' whether $V=L$, since by their very nature their operations are absolute to the $L$-hierarchy: running them in $V$ yields the same course of computations as running them in $L$. (What kind of 'computation' could it be that was not so absolute?) So without external oracle input say, as Joel points out, they will never produce anything beyond $L$. The remarkable result is that they nevertheless produce all the constructible sets. In one sense this was to be expected (at least for the Turing machine model): the original Hamkins-Kidder machines were known to compute (codes for) all levels of the $L$-hierarchy up to a certain level. This was only hampered by the $\omega$-length of their tape. Thus if you give them $On$-length of scratch/output tape, then there would be no stopping them!

As an additional reference there is a survey article Transfinite Machine Models in Turing's Legacy Lecture Notes in Logic vol 42, Ed. R. Downey, CUP; Apr. 2014.

As already explained by Joel and Philip, the machines you describe basically compute $L$. Still, there are natural principles connected with these machines that lead out of $L$: By a theorem of Sacks, if a real $x$ is (Turing)-computable relative to all oracles in a set of positive Lebesgue measure, then $x$ is recursive. Intuitively, this means that for a non-computable real $x$, randomly chosing an oracle is not likely to help in computing $x$. The analogous principle for Ordinal Turing Machines turns out to be independent from $ZFC$ and is in particular false in $L$: In fact, the halting problem for Ordinal Turing Machines is solvable relative to all but countably many real oracles in $L$.

• Merlin, can you sketch an argument of the independence result you mention? Do you have that written up? Jul 3 '14 at 21:40
• It is written up in this preprint with Philipp Schlicht: arxiv.org/abs/1307.0160 , Theorem 10 and Theorem 12. The idea for $L$ is simply that one can use any real $r$ occuring after the supremum of the halting times in the $<_{L}$-ordering as a "stopwatch" for $OTM$-computations: Let the program run, enumerate $L$ along the way, if the program has not stopped before $r$ was written, it won't. The other direction uses forcing. Jul 4 '14 at 13:04
• Very nice! It reminds me of some of the situations with descriptive set theory in infinite time computable model theory, where there was one kind of situation in L, but another (nicer) one obtainable by forcing or under PD. Jul 4 '14 at 13:12