Would Infinite Time Resolve the Halting Problem?

[nomadreid]

The short version: If you had an infinite amount of time, would the standard proof for the insolubility of the halting problem still work?
The longer version: A simple proof that there are non-computable functions can be easily seen by the fact that there are only countable number of Turing machines but an uncountable number of functions. Fine. But then one might think that if one had an infinite amount of time, then one could solve the halting problem by simply testing each pair, (program, input). That is, the halting problem is for finite automata, that is, where the procedures are of finite length, so that by presenting this "solution", one is effectively re-defining Turing machines, allowing them to be defined in terms of formulas that are of infinite length, allowing the set of the number of Turing machines to have the same cardinality as the number of functions from the integers to integers, thereby throwing the proof based on infinities out the window. However, the standard proof of the existence of non-computable functions rests not on the comparable cardinalities, but rather on the contradiction one would have if one said that allowed the sort of indirect self-reference stemming from "a Turing machine able to handle the output of all Turing machines". Why wouldn't this proof still work in this case? Or if it would, why wouldn't you be able to just tick off all possibilities in infinite time?

 

[.Scott]

The short version: If you had an infinite amount of time, would the standard proof for the insolubility of the halting problem still work?

Even if you give yourself an infinite amount of time - at therefor an infinite number of machine cycles - what does that mean. Do you actually ever get the answer?

Turing's proof is basically this (from wiki):

Informally, for any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do. No f can exist that handles this case.

In essence, what you are saying is that you want the computer to have N machine cycles available to it as N approaches infinity. In that case, the answer is "No" because N is never enough.

But you may say "But that's because N is always finite on its path the infinity". True enough, but the destination you envision does not exists. You are thinking that at some point N will reach Aleph Null, the countable infinity. But Aleph Null is a cardinality, not an ordinal.

But there is another way to slice this...

We could rank our f and g function according to how many nested g functions it needs to call in order to complete. We could then say that for any g.rank(M), there will be an f.rank(M+1) that can crack it - and the amount of processing cycles needed to complete a rank M process will always be a finite polynomial. So with unlimited time, M is also unlimited.

So "yes". At least in a sense.

 

[nomadreid]

Thanks for the answer, .Scott. A couple of comments. First, I see that my question was phrased in such a way as to envision the infinity in question to be potential rather than actual. I agree that a potential infinity would not be enough, which is why I meant an actual infinity. (I got the idea of actually completing the countably infinite number of cases from an article on hypercomputation which claimed that this might be theoretically possible, albeit not practically, given the right metric -- but since I have not quite figured out how that would work, I posed a corresponding question in another rubric.) In that case you would indeed get an answer, in that you will have either stopped when the program halts, or would have checked all cases for finite automata with finite inputs, the set of which would have cardinality aleph-null

 

[SSequence]

The short version: If you had an infinite amount of time, would the standard proof for the insolubility of the halting problem still work?

This is a somewhat subtle question, and to me the "standard response" to the question does not account for a number of subtleties . I have written about various aspects of this in a number of previous posts (in this forum) so I don't feel like it is a good idea repeating it over.

============

Regarding your main question, I don't quite get what you are trying to say. But there are two main points to it:
(1) The halt function not recursive/computable.
(2) Use of Church's thesis to extend/generalise the conclusion in usual way.

The proof of (1) can be thought of as a mathematical theorem. While it is true that it is sometimes written as proof by contradiction (which can cause someone to be a little skeptical that something might have been missed). However, it can be re-written (without much difficulty) in a rather direct way.

Also note that one can directly describe other simple non-recursive functions too (probably halt function can be thought of as more intrinsic for some reasons though). For example, order all total recursive functions (with or without repetition ... doesn't matter) using indexes of programs. And then just diagonalise.

=============

Regarding "hypercomputation", once again there are two different aspects:
(1) A certain kind of claim that non-computable functions can be calculated empirically.
(2) A mathematical development. It is obviously of value so there is no need to comment on it.

I will just comment on (1). The thing is that it is kind of a philosophical confusion in my opinion. I am NOT suggesting not searching for options to be able to empirically derive a large number of values for non-recursive functions (how plausible it it or isn't, let the relevant person(engineers,physicists etc.) decide).

What I am just saying is that the claim (the way it is stated) in (1) (interpreted in a strict sense) isn't coherent.
Here is a good general read in this regard which you may have already read (it has been some time since I read it, but I largely remember agreeing with the "main point"):
http://www1.maths.leeds.ac.uk/~pmt6sbc/docs/davis.myth.pdf

 

[nomadreid]

Thank you, SSequence, for your detailed reply. I will be looking for your earlier posts in this forum on this topic.
Although I had not read Davis' article (to which you kindly provided the link), I had seen the ideas he presented in other places. It is indisputable that, given the definitions and assumptions now in place for computability, hypercomputability becomes an empty notion. The question becomes whether, by extending the model from which the rules for computability may be satisfied, we can then non-conservatively extend the definition of computability. That is, computability is based on certain limits of the corresponding functions; if these limits are expanded to include higher infinities, another concept of computability (hypercomputability) would perhaps be possible, but it seems to me that by so doing, the halting problem would also be changed, so that although the sentences which the classical halting problem dealt with would become decidable, the changes allowing for this decidability would introduce new functions which could again be diagonalizable (that is the "self-reference" to which I was referring) , once again introducing undecidability. That is, I am wondering about the validity of the assertion "The set-up can be used to decide the halting problem, which is known to be undecidable by an ordinary Turing machine. All the observer needs to do is to prime the Turing machine to signal to p if and only if the Turing machine halts." in the article https://en.wikipedia.org/wiki/Malament–Hogarth_spacetime.
Although that article addresses the question as to whether or not such a model is physically possible, this is not my question. (After all, not only are such attempts not practical, even most "computable functions" are not realistically computable given the resources of the universe we live in. But mathematics is not limited to the axioms of our physical universe. )

 

[FactChecker]

If an algorithm has two states: "working on it", and "solved it", then you would need to formalize a transition to the "solved it" state in infinite time. The mathematical technique of transfinite induction is used in some proofs involving infinity. I wouldn't know how to apply it here.

 

[SSequence]

@nomadreid
In short, as per my limited knowledge, there are usually two ways to study the extension:
1-- make physical models that are supposed to involve a non-computable calculation
2-- define more sets in mathmatically streamlined fashion

With regards to (1), I think sometimes physical situations are also proposed for intractable or presumably intractable problems (one's with inefficient solution or no known efficient solutions). Though I think there is a difference in both in a sense. If you were to empirically realize a "solver" for intractable problems, you could "check" the solutions fast enough (Edit: I think only in some cases).
On the other hand, if you empirically realize a "solver" for undecidable problems, you can only check against mathematical statements considered/established as truth (or statements that are thought to be "nearly" true) --- and if it is a goldbach-type statement being declared true or false, try to check your best for inconsistency/consistency.

In any case, for (1) I think "usually" a fair amount of Physics knowledge (of the relevant domain) might be required to read a given essay/article. And judging both the "empirical plausibility" and "repeatability" of the given model might be a task that can probably only experts in relevant area decide best.

With regards to (2), you mentioned "higher infinities". I don't know what that means, but if it is any reference to cardinalities, then they come very late. And, as far as I know, some very difficult and subtle philosophical issues will arise with this (this is a big picture problem). I don't comment any further on this as this is very well beyond my scope.

The traditional extension of the notion of non-computability was done decades ago (with the prefix "higher" attached before computability or recursion theory) ... though I know nothing about it.

But the machine/program based approach (for a similar extension but using a different approach) is fairly recent. The usual way is to take either:
(i)--- turing/post model of computation
(ii)--- program based model (usual way is to extend register machines that use "goto" construct)

Then one simply extends the "time/duration" of computation to ordinal length. With this you just have to set the rules for how the:
(i) pointer position and cell contents
(ii) line number and variable values
will be settled on limits. One can go further and also do the following:
(i) extend the tape or workpad from length ω to ordinal length
(ii) extend the variable values from ω to ordinals

=================

These approaches are well-studied and you may want to read:
--- Prof. Joel Hamkins' paper on ITTM (ω-length tape)
--- Prof. Peter Koepke's number of papers regarding the program model and extension of tape/variable values

These references are obviously not meant to be exhaustive (by any means whatsoever).

To "fully understand" the said papers, you would need a strong enough background in both logic/sets and recursion theory (my background in logic/sets is non-existent and knowledge of (required) recursion theory insufficient).

 

[nomadreid]

To the last two replies: thanks to both Fact Checker and SSequence. Further:

First, to FactChecker: your reference to transfinite induction is interesting, but the proofs I know of using transfinite induction do not actually use an infinite number of steps any more than taking an integral requires actually going through a computation with an infinite number of steps. That is, with an appropriate set of axioms expressed with finite sentences, a finite computer could carry through many cases of transfinite induction. As someone (?) said, with infinite input it is not hard to get infinite output. Otherwise put, one treats infinities purely formally, as symbols in sentences, without worrying about their semantics. Syntax without the semantics which they would "seem" to demand. As far as a checker to distinguish "working on it" or "solved" in a problem that really does require an infinite number of steps, that is extending the "halt" of a Turing Machine to the transfinite, the first case would be when the collection of possibilities, the universe, had cardinality aleph-null, such as in the Goldbach conjecture: if one had an infinite amount of time and the checking of each possibility took only a finite amount of time, then one could just check each possibility, and in the end, after the infinite time had elapsed (using the Cantorian concept of infinity, not the ancient Greek one), one had checked all the possibilities, and there would have been either a case in which it was true, or not. However, if the cardinality is uncountable... I will have to think about that.

Second, to SSequence: Thank you also for the references. I have just downloaded the paper of Prof Hamkins to which you referred (presuming you meant https://arxiv.org/abs/1101.1864), a relevant paper of Prof. Koepke's ( http://www.math.uni-bonn.de/people/koepke/Preprints/Register_computations_on_ordinals.pdf ) and for good measure a couple of others on the topic (hss.ulb.uni-bonn.de/2013/3196/3196.pdf, https://arxiv.org/pdf/1307.6599.pdf), which I came across while looking for those first two. I look forward to reading them. Thankfully, I do have a background in logic and set theory, but alas, my background in recursion theory is scant. But I will try nonetheless. You are probably right that one's background in physics needs to be relatively strong to read the corresponding papers in the prospects of physical realizations, and my physics background probably is not up to it , which is why I am concentrating on the mathematical side. (My physics background is strong enough to be distrustful of physics popularizations, but once you weed out the dubious statements in such articles, what is left is still sort of fun )

Yes, of course any statement of truth/falsity is only relative to the axioms and models (domains of the variables), and although there is a class of problems that can be posed in provably consistent axiom systems (Presburger arithmetic, for example), most other interesting problems (e.g., Goldbach) will be based on a form of arithmetic over the natural numbers which enjoys a high confidence of consistency.

My sentence in the original post containing the phrase "higher infinities" was written hastily: I meant simply "infinities", not only the higher ones (i.e., referring to those with cardinalities greater than aleph-null, or ordinals greater than ω: of most interest, of course, is the continuum) but also aleph-null and ω. My apologies for the slip.

 

[SSequence]

Regarding the first paper, this is not the paper I was referring to (and the one you linked to might be advanced). Anyway, I will link to it.

Also Prof. Koepke has number of papers (both on introducing program model and extended tape ITTMs I think). Here is a bit of terminology (regarding the program model) that might help you sorting which ones you should read first (and may be easier than others):

ITRM (register machine model) (some variations in limit conventions)
runtime=extended
variables=limited to less than ω

ORM
runtime=extended
variables=extended

Also before reading extended tape ITTMs (in full detail), it might be a good idea to read the ones with limited tape:
https://arxiv.org/abs/math/9808093
https://arxiv.org/abs/math/9907044

========

I should add that I haven't read these (partly due to background reasons I mentioned) and so I am not familiar with the contents (in detail that is) ... so I have to add that I may have missed some further important distinctions.

 

[nomadreid]

SSequence, thanks for the two papers and the mini-glossary. I have downloaded them, and I now have lots to work through. Great!
And yes, I saw that Prof. Koepke has a number of interesting publications, and I will probably go back to his list of publications after working through the others.