Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If we had a computer that could perform a countably infinite number of steps of a Turing machine, what currently open problems could we solve? I guess a lot of number theory problems could be solved just by verifying it for each $n$. But presumably some problems wouldn't be checkable in a countably infinite number of steps.

In response to the comments let me say that I'm not saying "Hey check it out, I have an oracle, what should I ask it?" I'm asking "What kinds of problems can be check by what kinds of computing devices?" For finite domains, your standard Turing machine can prove a lot. Fine. And presumably some problems wouldn't even be checkable with a countable supertask (if I may talk like that). So what is the difference between these classes?

Note I'm asking about mathematical problems that could be verified this way, so this is on topic and shouldn't be migrated to TCS.

(better tagging suggestions welcome)

share|improve this question
1  
Since no computer, or any finite number of computers, can perform an infinite (countable or not) number of computations, I don't see how any result that required an infinite number of computations could be practically attainable. –  ItsNotObvious Jan 18 '12 at 15:17
4  
Any problem of the form "does (recursively axiomatized) theory $T$ prove statement $p$?" –  Chris Eagle Jan 18 '12 at 15:17
2  
If $p$ is a predicate and $p(x)$ can be checked in countably many steps for any element $x$ of the countable set $X$, then any theorem of the form $p(x)\forall x\in X$ could be settled. Maybe it's more interesting to ask about what can't be settled. –  Chris Taylor Jan 18 '12 at 15:18
2  
This is a nice article, which says Riemann hypothesis and Jacobian conjecture could be decided, but currently it is not known if $P=NP$ is equivalent to a $\Sigma_1$/$\Pi_1$ sentence. –  sdcvvc Jan 18 '12 at 16:49
2  
Couldn't "every" problem be solved? Just produce a list of all provable statements in ZFC and look whether your problem or its negation is among them. And why does verifying $P(n)$ for all $n$ prove that "$\forall n P(n)$" is true? Such an algorithm wouldn't produce a proof of "$\forall n P(n)$". –  Michael Greinecker Jan 18 '12 at 17:25

5 Answers 5

up vote 20 down vote accepted

The infinitary computability concept that you describe sounds fairly close to the concept of infinite time Turing machines, which extend the operation of ordinary Turing machines into transfinite ordinal time, and thereby provide a robust mathematical model of supertask computation. The basic idea of the ITTM model is to allow an ordinary Turing machine to operate into transfinite ordinal time, by defining the limit configuration and allowing it continue its operation. At successor ordinals, the machine operates according to the rigid instructions of its finite program. At a limit stage, the head is reset at the left-most cell, the new state is a special limit state, and each cell of the tape is updated by taking the $\limsup$ of the values displayed in that cell going into the limit.

The principal reference is my paper with Andy Lewis: J. D. Hamkins, A. Lewis, "Infinite time Turing machines'', J. Symbolic Logic 65, 2000, p. 567-604. The machines were first defined by Jeff Kidder and myself.

In the ITTM model, we investigated both the complexity of the sets that are infinite time decidable, as well as the lengths of time that such computations take. It turns out that not only are all arithmetic sets infinite time decidable---and so all the arithmetic questions of number theory are decidable by such machines---but the collection of infinite time decidable sets reaches nontrivially into the projective hierarchy, beyond the hyperarithmetic sets $\Delta^1_1$ and indeed beyond the lightface analytic sets $\Sigma^1_1$ and into the $\Delta^1_2$ sets. So much more complicated questions can be settled by these machines. For example, with infinite time Turing machines one can test a countable order as to whether it is well-founded, which is in general a complete $\Pi^1_1$-test. In the ITTM context, there is a very interesting theory concerning the supremum of the lengths of the halting computations in comparison with the lengths of the stabilizing computations in comparison with the lengths of the not-yet-repeating computations. The ordinals where these phenomena occur are known as $\lambda$, $\zeta$ and $\Sigma$, and they are intimately connected with certain fine-structural features of the constructible hierarchy. For example, Philip Welch proved that $L_\lambda\prec_{\Sigma_1}L_\zeta\prec_{\Sigma_2}L_\Sigma$, and the ordinals are characterized as the least triple of ordinals with that property, a result that has become known as the $\lambda$-$\zeta$-$\Sigma$ theorem.

The arithmetic sets are exactly those sets that are decidable uniformly in time $\omega^2$, with each limit giving you essentially two additional arithmetic quantifiers. The hyperarithemtic sets are exactly those sets uniformly decidable in time less than $\omega_1^{ck}$, the supremum of the computable ordinals. Meanwhile, the clockable and writable ordinals reach far higher than this.

Not all sets are infinite time decidable, of course, since there are still only countably many programs and thus only countably many decidable sets. Indeed, there is an infinite time analogue of the halting problem, which is infinite time semi-decidable but not infinite time decidable. There is also an analogue of the Turing degrees for this context, with two jump operators, corresponding to the boldface and lightface halting problems, for which one either allows or does not allow real parameters.

You may consult this list of my further articles on the topic, whose bibliographies contain references to the increasingly large literature on the topic. There are now infinite time analogues of computability theory, complexity theory, equivalence relation theory and much more.

share|improve this answer

You would be able to check whether our axiomatic systems are consistent or not, since a contradiction is a deduction of finite length.

share|improve this answer

There are lot many problems that you can solve, in case if you have any such magical machine with you. To name a few ( very famous problems ! )

  1. $3n+1$ conjecture can be one among them, as you need to verify whether every number leads to one if passed through the pipe ( by pipe here I mean flow ) of functions defined by the conjecture . So as you can check for infinite numbers with the so called " magical machine " you have with you. If you want to read about this conjecture read it here.
  2. You can also proved the " Famous Fermat's Last Theorem ", which baffled mathematicians for years. As you need to prove that there are no solutions to Fermat's Equation $x^n+y^n=z^n$ if $n\gt 2$ for infinitely many numbers. But that proof has been settled by Prof.Andrew Wiles recently. $\backslash$If you take it for fiction, in a humorous way I can say this, if you want to prove the F.L.T now, with your " Magical machine ", its too late now, but you need to have some other thing in addition to the machine you have, thats called " Time Machine " , so the thing you can do is to go to the time before Prof.Wiles has born, and fix the solution there, you would be famous then ! , but regarding time-travel ( one of my interesting subjects ) there are many theories I have read ( due to Einstein, Hawking etc. ) which say that Time travel can be possible, but there are lot many paradoxes and mysterious mind-blowing problems in time travel that can't be solved with your machine , :) .
  3. And I think there are numerous problems concerning primes, like " Existence of infinitely many primes of form $n^2+1$, are there infinitely many twin primes ? ....Blah Blah... I think it this space wont be sufficient to write up all those things here, see this.

But as to generalize what I said above , you can solve lot many problems, by using any such machine, and I think there is no such machine. If any such machine exists then the major conjectures in number theory can be solved, as much of them involve checking for all $n$ as you have said.

So its not possible to mention all those conjectures here, what the thing you can do is to collect a list of conjectures from your " friend " google, and filter all the ones that have a parameter to check for all numbers. So just to initiate I have stated $3$ problems, but there are many conjectures . So if anyone still have patience and time to write are always welcome to add a new answer.

Thank you , and I hope that you invent any such machine one day, which would facilitate mathematicians to solve problems more easily. But to add, imagine how hard is to invent such proofs without any such machine. That's the greatness of Man, a human brain is equal to millions of computers in thinking capability, and beauty of number theory lies in settling the proofs of such beautiful conjectures without taking any aid of any such infinite-magical-machines you have told about. Humans do that with just a proof that is convincing. That's the beauty of mathematics.

I can end this up with a last sentence " Computers don't have common sense ", :) .

Bye.

share|improve this answer
    
Does the Collatz Conjecture actually work on such a machine? I'm taking the 'super machine' as being essentially a $\Sigma_1 / \Pi_1$ machine, as sdcvvc suggests in the comments on the question - that is, essentially a machine that can 'do a finite amount of work for infinitely many numbers'. But I don't see an easy interpretation of the Collatz conjecture as such a statement, since any given number might have an 'infinitary' path; essentially Collatz asks 'does there exist a number $n$ s.t. there does not exist a number $k$ s.t. $C^{(k)}(n) = 1$?', a $\Sigma_2$ statement... –  Steven Stadnicki Jan 18 '12 at 18:30
1  
@StevenStadnicki I think that would depend on how the hypothetical machine would behave if given a problem that doesn't halt. If all numbers satisfy the conjecture all is good. Any number that doesn't satisfy the conjecture would either end up repeating the sequence (in which case no problem because this is a halting condition that disproves it); or never terminate while never repeating itself (Side comment, would calling this sequence transcendental be correct?). In more CS terms; could the machine solve the halting problem? –  Dan Neely Jan 18 '12 at 20:08
    
Concerning the Collatz-question: in the other question of Steven I've reformulated the cycle-problem in the Collatz such that it can be done by such a supertask-machine. math.stackexchange.com/questions/100218/… There is a representation which avoids the analysis of a -possibly- infinite/circular trajectory and allows a finite enumeration of rational solutions for each cycle-length.(There's also a link to J. Simons'/B.de Weger's article - see also wikipedia for more) –  Gottfried Helms Jan 21 '12 at 6:11

Forever Is a Day: Supertasks in Pitowsky and Malament-Hogarth Spacetimes discusses about hypercomputation of Fermat's Last Theorem -albeit certain technical background is needed to understand the details.

You can also google Malament-Hogarth spacetime. Here is another paper that discusses the question.

share|improve this answer
    
It might even have been reading that very paper that got me thinking about this. But I'd forgotten about it… –  Seamus Jan 21 '12 at 10:07

I don't think it is completely well-defined exactly what "perform a countably infinite number of steps of a Turing machine" means.

One natural interpretation would be that we're allowed to ask an oracle whether a standard Turing machine of our choice terminates or not, and get the correct answer in unit time. (We can quibble a bit about whether the oracle ought to be able to distinguish between different kinds of non-termination -- but it is unclear whether that can be strictly justified as merely "doing infinitely many steps"). This appears to be the interpretation tacitly employed by the other answers, and would "merely" mean that we get access to one next level in the arithmetical hierarchy.

On the other hand, one could also ask whether an oracle machine of the kind outlined above itself terminates. And we might then imagine a meta-oracle that answers that question and consider what one can compute with access to the meta-oracle. (See also Turing jump). The total number of steps performed at the lowest level is still countable in this model, because $\aleph_0\times\aleph_0=\aleph_0$. And, a fortiori, one could argue that "perform a countably infinite number of steps" ought to be interpreted to allow any number of stacked oracles.

These considerations suggest that instead of merely speaking about the cardinality of the steps we're allowed to perform, we should speak about a limit on the ordinal number of the steps we can do. A standard Turing machine would then be one that is required to stop in less than $\omega$ steps. A machine that must run for less than $\omega+\omega$ can be viewed as one that can afford to ask one question of a standard halting oracle; but if need to stop before $\omega\times\omega$, you can afford any finite number of question to the standard halting oracle. Higher ordinals yet will allow meta-oracles, meta-meta oracles and so forth.

The details of defining exactly how such a transfinite Turing machine would operate are left to the enterprising reader -- especially figuring out a way to define a state and tape the machine would have if and when it reaches a limit ordinal.

With a large enough ordinal you can probably reach the entire arithmetical hierarchy up to any finite height, but I think that may be as far as it goes. We can't hope to get into the hyperarithmetical hierarchy with any reasonable definition of how the transfinite machine should behave, because there are sets there that are not arithmetically definable, period.

share|improve this answer
    
Henning, regarding the question of whether supertask machine concepts are limited to the arithmetic hierarchy, please see my answer. –  JDH Jan 21 '12 at 2:30
    
@JDH, very interesting! My hazy ideas about handling limit ordinals involved having an auxiliary stack of (tape,state) pairs which could be pushed explicitly and popped off automatically when a limit was reached -- by analogy with the oracle machines, this was supposed to give the surviving machine only one bit of information saying "there was a diverging computation here". However, destroying all other information in the diverging computation makes my model much weaker than yours; I think mine would stay arithmetical up to at least $\epsilon_0$ or thereabouts (perhaps even $\omega_1^{CK}$). –  Henning Makholm Jan 21 '12 at 5:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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