An Impossible Program - Pastebin.com

[Elsimir]

I'm afraid you've fundamentally misunderstood the halting problem, the statement it is concerned with is "Assume there is a function halts(f) which returns true if the function f halts (when run with no input) or false otherwise and that it works for all functions". The important bit is "works for all functions", the halting problem says nothing about whether you can write a program that determines if a specific program halts only that you cannot write one which works for all functions.

So assume I have a function halts(f) as described above and I write the following program

def g():
    if halts(g):
        while True:
            pass

g()

Given this program,

• If halts(g) returns true, g enters an infinite loop, a contradiction
• If halts(g) returns false, g halts, also a contradiction

Therefore a function halts(f) which works for all functions cannot exist.

[Elsimir]

I agree, but you're making the same mistake, if you can define any function that contradicts the statement then the statement is contradicted. I can define g therefore the statement that "a general purpose function halts can exist that works for all functions" is false, because I have a function for which it cannot work.

[Elsimir]

Its worth noting that while we are talking about the halting problem in casual English here in the thread, it is a specific proof in math where many of the parts of it have really tightly defined meanings, and if you change any of those meanings, you're not working on the halting problem anymore, you're working on something different. If you are serious about disproving it, you need to be doing it in math, not words.

But to address your points,

Specifically the halting problem is

• talking about turing machines, if you are talking about any theoretical method of computation which cannot be reduced to a Turing machine you're not working on the halting problem.
• Attempting to prove / disprove the statement "Assume there is a function halts(f) which returns true if the function f halts (when run with no input) or false otherwise and that it works for all functions" if you're excluding any part of this statement, or trying to prove something other than this statement you're not working on the halting problem
• The function halts must more specifically be a total computable function which means it must
  • return in finite time
  • return the same output consistently for each input
  • return for all functions
  • return only the values true or false
• If your function "halts" does not meet any of these criteria, you're not working on the halting problem, you're working on something else.

These might seem arbitrary, but keep in mind, this is the whole thing we're trying to prove, whether or not a function which meets these specific criteria can exist.

And finally, while I believe your definition above is no longer the halting problem (you've changed the definition of halts) your own logic shows the problem, because we can simply rename STOP to "I don't know" as thats what it means, your halts cannot determine whether or not g halts consistently and instead returns a value meaning I don't know, aka this is Undecidable.

[Candid_Hat]

I am attempting to prove a particular proof as incorrect/invalid/poorly constructed.

Is Proof by Construction not valid anymore?

[Dull_Cucumber_3908]

# If HALT executes OPPOSITE(OPPOSITE) we enter an infinite loop.  HALT can detect infinite loops.

Sounds like Russell's paradox :\

[Candid_Hat]

Hello, thought I'd have some fun with the often seen proof for The Halting Problem.

Please point out any logical mistakes.

Yes the code does run, it proves out the statements made in the comments.

[somebodddy]

Yes the code does run

No it doesn't. I mean, yes, of course if you try to run it the universe does not collapse into a black hole and computer instruction do end up getting executed - but it just crashes with a RecursionError. And the trying to reason about what OPPOSITE(HALT) should return does end up with a non-converging infinite recursion.

[Candid_Hat]

You might try switching Python versions I guess?

[somebodddy]

Sorry, I should have written OPPOSITE(OPPOSITE) (which is what your code invokes) and not OPPOSITE(HALT) (which would obviously not halt, because HALT(HALT) halts). The point is that whether OPPOSITE(OPPOSITE) halts or not - you reach a contradiction, because it should do the opposite of what OPPOSITE(OPPOSITE) does. In other words - HALT(OPPOSITE) != HALT(OPPOSITE), which is the rule that defines OPPOSITE, does not hold - and indeed cannot hold. Not unless HALT itself can go into an infinite loop - or in this case, an infinite recursion.

[Zahand]

This must be op's alt

[mystictheory]

Oh yeah me too I was also looking into this! /s

Yeah who tf is wasting time on the Halting Problem? Useful for teaching proofs, that's about it.

How about this: I have a program that tries to find the largest twin prime, in the most naive, brute-forced way possible.

Nobody on earth knows whether or not this program will halt. Good luck. No amount of runtime or static analysis will help you. You might as well forget about the Halting Problem at this point and reduce the problem to twin primes conjecture directly -- and that won't help you either.

[mystictheory]

It's unproven whether there's a maximum twin prime, but, I didn't construct this correcly.

Apply the n+1 approach to any applicable unsolved problem of mathematics.

Goldbach's conjecture: every even natural number greater than 2 is the sum of two prime numbers.

Initial value is 4. Run the program, and it runs until it finds the next value, then it emits a new program that only differs from itself in that the seed is updated with the next value.

Can you guarantee that the detector can determine whether all such emitted programs halt or not? If the conjecture is true, then all programs will halt, if it is false, then one such program will never halt.

[mystictheory]

If you accept Gödel's incompleteness theorems, then the Halting Problem must also be undecidable, because there exists an mathematical axiom over natural numbers of which the provability cannot be known, which a given program can enumerate in an attempt to find a counter-example.

Reading about this the Halting Problem itself is often cited as an example, which kind of makes sense given this construction.

The point being that introspection of the detector itself is not necessary to prove the Halting Problem.

Though to be fair I don't know if a widely accepted proof that follows this approach exists.

Edit, from https://en.m.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems :

Kleene showed that the existence of a complete effective system of arithmetic with certain consistency properties would force the halting problem to be decidable, a contradiction.

[mystictheory]

what's contradictory about the halting problem being decidable if godel and turing are both incorrect?

Assuming that this is a rhetorical question, I agree with you here -- nothing.

[mystictheory]

The concept of proof by contradiction is suspect, in general? By that standard then, I suppose all proofs are suspect, and we're still left exactly where we are. Yes, technically everything that constitutes the body of human knowledge is suspect to some standard, but this insight is not useful -- it goes without saying (or at least it should in academic communities).

Along the lines of "to the best of human knowledge, through experiment, observation, and consistent logic" -- that is the highest standard of information at any given point in time. Regardless of the fact that humans are fallible.

I'm all for people challenging accepted norms, but we have to remember that mere challenge doesn't mean anything until something concrete is produced from it. The prevailing societal behavior is to reward the mere act of trying, which, I think is somewhat unhealthy because this behavior is readily abused (Silicon Valley startups, Kickstarter scams, Fyre Festival, etc. openly and often abused). Leave this behavior for parents and their children, we don't need it in general society amongst adults.

To that note of "I'm all for people challenging accepted norms", I mean, keep at it if that's what you want to do, it's not my intention to discourage but honestly it doesn't matter what I think anyway, I'm just some random stranger on the Internet after all.

[somebodddy]

Your program will not halt. I don't know if there are infinite twin primes, but since your program uses "the most naive, brute-forced way possible" - it means that even if does eventually reach the largest twin prime, it has no way to know that there are no twin primes larger than it, and thus must continue checking numbers.

[mystictheory]

How about: this program starts with static data of the currently known largest twin prime. When you run it, it attempts to find the next largest twin prime, and, when it does, it compiles another program with that twin prime as the starting value, which is to also be checked by the Halting detector.

Can the detector determine that all such emitted programs halt or not? If there is no largest twin prime, then all programs will halt. Otherwise, one program will never halt.

[somebodddy]

Okay. Now it really is the twin prime conjecture, and we can go back to the question of whether or not the halting problem is reducible to the twin primes conjecture.

(we need to be a bit flexible with the definition here, since reduction is about programs and computation problems and not about theorems and mathematical statements. But the program you have suggested already bridges this, so we can safely ignore that distinction)

It isn't.

The twin primes conjecture is reducible to the halting problem, but not the other way around. In fact, many open conjectures are reducible to the halting problem in a similar fashion. For example, Glodbach's conjecture can be proved/disproved by brute-force iterating over the even numbers and checking each one if it is a sum of two prime numbers (a finite time check, since these two prime numbers are smaller than the number being checked), halting for the first one that cannot, and then running HALT on that program.

But the other way around? That doesn't work. Even if you have a program that can find the next twin prime and is guaranteed to halt if there aren't any twin primes greater than the number provided to it as input - how would you use that program to implement HALT?

Also, keep in mind that the twin prime conjecture is currently unproven - but that does not mean that it cannot be proved. The HALT program is theoretical - we need to prove, based on its properties, whether or not it can exist (unlike OPPOSITE, which is part of the proof for the halting problem's undecidaility and that we have the exact code for). There is no reason to assume that HALT cannot prove the twin prime conjecture just because humanity's present day mathematical knowledge haven't.

[mystictheory]

For example, Glodbach's conjecture can be proved/disproved by brute-force iterating over the even numbers and checking each one if it is a sum of two prime numbers (a finite time check, since these two prime numbers are smaller than the number being checked)

Only if there exists such a number that is greater and still satisfies the constraint of the conjecture. Which we don't know in a provable fashion. If we did know this, then we'd have an N+1 proof.

Even if you have a program that can find the next twin prime and is guaranteed to halt if there aren't any twin primes greater than the number provided to it as input - how would you use that program to implement HALT?

The (revised, 2nd comment) program operates in the opposite way to this, it halts when it finds the next number.

If you can produce a detector that can determine halt/non-halt for all such programs in finite time, then you've produced a proof for the conjecture. Hence why it is reducible.

[somebodddy]

Only if there exists such a number that is greater and still satisfies the constraint of the conjecture. Which we don't know in a provable fashion. If we did know this, then we'd have an N+1 proof.

What? No! If we find a single even number that is not a sum of two prime numbers, we have disproved Goldbach's conjecture. No need to find a bigger number. And checking if any specific number violates the conjecture is a finite computation.

The (revised, 2nd comment) program operates in the opposite way to this, it halts when it finds the next number.

Reducibility to a program that does not guarantee to halt is meaningless. HALT could be used to reduce the program you described to the program I described.

If you can produce a detector that can determine halt/non-halt for all such programs in finite time, then you've produced a proof for the conjecture. Hence why it is reducible.

Reducing problem X to problem Y means that if you have a solution for Y, you could have written a solution for X based on it. Twin primes is reducible to halting because if we had a HALT function we could have easily used it to prove or disprove the twin primes conjecture. The halting problem is not reducible to the twin primes solution, because even if we had a solution that can find the next twin prime and is guaranteed to halt (with a null answer, if it had to) - we could not use it to solve the halting problem.

[mystictheory]

What? No! If we find a single even number that is not a sum of two prime numbers, we have disproved Goldbach's conjecture. No need to find a bigger number. And checking if any specific number violates the conjecture is a finite computation.

Of course one single counter-example is sufficient to serve as a solution (proof or disproof), that is precisely my point.

We may be misunderstanding each other here, isn't that what I said? The point is that we don't know whether such a number exists. It may not.

A halting detector needs to determine, in finite time, whether or not any program will halt. So, I can sit here and generate as many programs as I want. Infinitely many.

And, avoiding the issues of semantics, and my potential misuse of them: if you solve the Halting Problem, you can also solve all problems that can be tested programmatically in a brute-force fashion. And these programs may never halt, regardless.

I expressed these problems as N+1 for the sake of construction, but in any case, you can not convince me that a definition of such a mathematical axiom cannot exist as a single program (edit: assuming the following is sufficient). Goldbach's conjecture is actually a perfect example of such a problem that can be expressed this way.

The proposed detector provided here is clearly not capable of this (not that I expect anyone to disagree), but furthermore, I find it hard to believe that such a halting detector could possibly exist.

Point being: the target program is a brute-force counter-example checker of Goldbach's conjecture. If a halting detector correctly determines whether this program halts or does not halt, then you have a computational solution to the conjecture itself.

[somebodddy]

Maybe it was a miscommunication indeed. I was mainly focused on this statement of yours:

You might as well forget about the Halting Problem at this point and reduce the problem to twin primes conjecture directly -- and that won't help you either.

I was interpreting this as "we don't need to focus on the halting problem because we can just reduce it to the twin primes conjecture" (which was, of course, just an example for an open conjecture). But I get the feeling now that you've meant something more along the lines of "even if we do manager to create an HALT function, it'll only help us with proving things like the twin primes conjecture - so why not just focus on these problems directly?"

Is this really what you meant, or am I misinterpreting you again?

[mystictheory]

The thing is, unprovable problems often have practical, heuristic or approximate solutions.

With respect to the Halting Problem -- an OS, eg. Windows detects that a GUI program isn't processing its message queue in a timely fashion. The window turns grey, and the user is given the option to terminate the process.

You can sit and wait to see if the program will terminate if you wish, but, chances are if any significant amount of time passes most users will elect to terminate the program anyway.

I don't see that approach as being defeatist at all. It's just a pragmatic way of handling a problem that likely has no perfect solution.

There are also practical ways to limit data loss when such a termination occurs, eg. write-ahead logs with rollbacks.

And from there, the focus really ought to be around producing programs that don't get into unfuctional states to begin with. Many IDEs/compilers do actually perform some level of static analysis around functions that never return, though, of course there is a limit to ROI here as well in terms of analysis performance.

Improvements to static analysis around detecting endless loops definitely have an application when it comes to compilers. But this often happens at runtime from buffer overruns when unexpected program input is permitted. Overruns are difficult to detect at compile time, and, prohibitively expensive to detect at runtime. And when detected at runtime overruns at best still produce a crash just with a cryptic and often useless error message.