[Math] What set theoretical questions could never be answered by Turing machines of arbitrary cardinality

computability-theoryfoundationslo.logicset-theory

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.

Best Answer

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.

Related Question