5 ms·

The article uses an intuitive approach trying to find a way to crack the halting problem. But the truth is that halting dilemma is real and despite any attempt

The article uses an intuitive approach trying to find a way to crack the halting problem. But the truth is that halting dilemma is real and despite any attempt to "unwind" or "simplify" the control and data flows, there is a real barrier. It is in the math. My favorite example: finding an odd perfect number. Euler stated: "Whether (...) there are any odd perfect numbers is a most difficult question". More recently, Carl Pomerance has presented a heuristic argument suggesting that indeed no odd perfect number should exist. [1] Does it exist? Definitely. Somewhere in 10^300 range. What is the exact value? Nobody knows. You can write a program that finds an odd perfect number: def odd_perfect_number(): n = 1 while True: if sum(filter(lambda x: n % x == 0, xrange(1, n))) == n: return "OK! I FIND IT!" n += 2 Will this program ever complete? Maybe. However nobody can say for sure. Avoiding recursion or some kind of groups won't give you any favor. This is the halting problem in all of its glory. [1] https://en.wikipedia.org/wiki/Perfect_number https://en.wikipedia.org/wiki/Perfect_number

cortesoft 6y ago
If it definitely exists, don't we then know that this program will definitely halt?
- garganzol 6y ago
  Only from algebraic and philosophical standpoints. This knowledge is not 100% precise unless a specific number is found.
  - groby_b 6y ago
    Nobody cares about the halting problem from a specific standpoint. If it's algebraically guaranteed to halt, it halts. When it halts is entirely meaningless for purposes of the halting problem. But the thing is, it isn't algebraically guaranteed either - we still don't know if an odd perfect number exists. (I'm not sure where the "Definitely. Somewhere in 10^300 range." is coming from. There's nothing definite about the existence, only constraints that need to be satisfied if it exists)
    - cortesoft 6y ago
      In fairness, though, the halting problem doesn't care if you can predict if SOME programs halt... you have to predict if ALL programs halt.
      - groby_b 6y ago
        There's that, too. (Well, we don't have to predict anything. We have to show that halting or not is a decidable condition, and we've shown it isn't. Even if we had shown it was decidable, there still might be programs where we practically can't figure out it halts. So is the beauty of math - it gives us the gestalt of the world without caring about the world :)
    - ProblemFactory 6y ago
      > Nobody cares about the halting problem from a specific standpoint. If it's algebraically guaranteed to halt, it halts. When it halts is entirely meaningless for purposes of the halting problem. Halting problem from a specific standpoint is a popular area of research. Microsoft Research in particular has been active in this area, and Windows device drivers and other kernel event handlers are analyzed to prove that they will halt in a reasonable amount of time to avoid locking up the OS. https://www.microsoft.com/en-us/research/publication/t2-temporal-property-verification/ https://www.microsoft.com/en-us/research/publication/t2-temp...
  - greydius 6y ago
    If you've prove a finite upper bound,then you've proven the program will halt. You don't need to know what the exact number is.
    - garganzol 6y ago
      The trick with boundaries does not stand true for evasive predicates on unbounded data. Please note that suggested odd perfect number search algorithm in Python uses an evasive predicate on a big integer which is unbounded. This means that a typical tracer (or verifier in Turing terms) won't be able to infer the upper bound for the given example.
cortesoft 6y ago
The best way the halting problem was explained to me was to think of it like this: imagine you write your perfect halting detection program. It reads in the contents of some program, and returns true if it halts or false if it doesn't. Now, all I have to do is write a program that includes an embedded version of your program. My program reads in the contents of itself and passes it to the embedded program. Now, all my program has to do is take the output of the embedded halt checker, and do the opposite; if the halt checker says the program halts, just keep looping. If it says I don't halt, exit immediately. Now, you might think this is cheating, because it is using your own program against you. However, this is at the core of the problem; it has to work for ALL programs, even ones written with knowledge of your program.
- galaxyLogic 6y ago
  Doesn't this assume that your program can reliably access it's own source-code? Can it? It can of course read some file containing some source-code. But assume it accesses some file which contains the source-code of some other program, then wouldn't your logic still hold the same, since from the point of your program it is simply reading some file?
  - cortesoft 6y ago
    Even if it can't access its source code, you can... you know what the code is
  - pjc50 6y ago
    Doesn't matter. Doesn't have to be the executing source, can work with compiled representations; the original Turing paper "compiles" every program to a single giant integer.
  - kazinator 6y ago
    No, it has nothing to do with source code. The halting verifier program V never accesses itself. It takes two parameters: a program to check for halting (P) and an input to the program (I). It's job is to test whether P(I) (the program applied to the input) will halt. To trick the halting verifier V we construct a diabolic P like this: program P(I) { if (V(I, I) == YES) { // if Verifier says I(I) halts inifinite_loop(); // ... then do *not* halt } else { halt(); // ... otherwise halt } } Like V, P is a special program that takes a program as input. It then asks the verifier: if the input program is given itself as input, does it halt? And then it behaves in the opposite manner: if the verifier says that I(I) halts, then P deliberately infinite-loops. Otherwise P halts. Given that P, we ask the verifier the devastating question: V(P, P). Does P halt if given itself as input; does P(P) halt? V cannot decide. Note that if we consider P(P), then it means that in the above program, the input parameter I becomes P itself: I = P. And so the V(I, I) == YES expression is actually testing V(P, P) == YES. But V(P, P) is the devastating question itself! If V(P, P) yields YES (P(P) halts) P goes into an infinite loop (P(P) in fact fails to halt), and so V has calculated the wrong answer: the actual behavior of P(P) contradicts the YES answer from V(P, P), rendering V incorrect. The same problem occurs if V(P, P) yields NO. Note that P contains no self refererence. The fact that P is applied to itself as P(P) doesn't come from P; it comes from the way P is used. P is used that way when we ask the verifier V(P, P). The verifier itself is checking what happens if P is given itself as input. P can happily accept other programs as the input I, programs which are not itself. What P needs is a way to embed V, because it relies on it. The assumption is that whatever halting verifier V someone tries to develop, it has to be public. So that is to say, some CS researcher claims he or she has developed a universal halting verifier algorithm V and they publish it. Then, promptly, their adversary takes the algorithm V and sticks it into their program P(I) as a subroutine, and has an instant test case which defeats V. The tricky thing is not self-reference, but the fact that P contains the verifier and turns it against itself. The self-reference is instigated from the outside by choice of inputs. In other words, the devastating question V(P, P) is what perpetrates the self-reference which breaks V.
saagarjha 6y ago
> Does it exist? Definitely. I am unsure how you reached this conclusion?
deleted 6y ago
[deleted]
jondgoodwin 6y ago
Author here. Cool story about odd perfect examples. That said, my post is not trying to find a way to crack the halting problem, and thereby demonstrate it is not real. Turing wrote a most excellent proof, and I stand by it wholeheartedly. I even cite another famous numeric example of a program we still do not know if it will terminate for all numbers: the Collatz conjecture. Notice my description: "Turing proved that no general algorithm can be formulated that can answer this question across all possible programs." The operative part here is "across ALL possible programs". The proof does stop us from knowing that SOME programs will or will not halt. It only stops us from being able to determine this for EVERY possible program. My post explores a very specific subset of programs that we can prove will terminate, then asks what pattern(s) underlie such programs, and then explores the use of such patterns in a variety of interesting problems. It is this last result that most intrigued me, and caused me to write about it.
- jondgoodwin 6y ago
  Important mistype. It should read: "The proof does NOT stop us from knowing that SOME programs will or will not halt.
  - jpt4 6y ago
    It does however apply to more properties than merely halting: https://en.wikipedia.org/wiki/Rice's_theorem https://en.wikipedia.org/wiki/Rice's_theorem
  - jpt4 6y ago
    You may also be interested in Willard's Self-Verifying Theories: https://en.wikipedia.org/wiki/Self-verifying_theories https://en.wikipedia.org/wiki/Self-verifying_theories
- j-pb 6y ago
  A bit tangential, but turings proof only works with some very strict assumptions. - Clasical logic as the foundation for math. - Proofs by contradiction work. - That the church turing thesis holds. I guess these are kinda two sides of the same coin. But still worth noting.
froh 6y ago
Interesting. Nitpick: Odd perfect numbers are no more in the 10^300 range but nowl provably beyond 10^1500. The Wikipedia links to a math paper to that extend.
dzsekijo 6y ago
Sorry to say, this example has nothing to do with the halting problem. Rather, I would say, it's a reformulation of a(n unsolved) mathematical problem to the question whether a certain function halts on a certain input (being "no input", as the function is nullary). Or, if you insist, we can regard it as a trivial instance of the halting problem. An instance of the halting problem asks, given (a partial recursive) function F, whether there is an decision algorithm A (aka. Boolean valued algorithm) on the universe of inputs U of F that calculates the domain of F (those inputs where F takes a value, ie. halts; ie, A(x) <=> F halts on x, where x in U). For any finite subset S = {s_1, ..., s_n} of U, there is a trivial decision algorithm on U that calculates S: def A_S(x): for s in (s_1, ..., s_n): if x == s: return True return False Therefore if the domain D of F is finite, the answer to the halting problem of F is trivially yes: A_D is a decision algorithm for F. (This has noting to do with the question whether we know D or not!) If U is finite, then D is finite, so the answer to the halting problem of F is trivially yes. If F is a thunk (nullary function), then U is finite, ie. the singleton set of "no input", so the answer to the halting problem of F is trivially yes. odd_perfect_number is a thunk.
- tom_mellior 6y ago
  > An instance of the halting problem asks, given (a partial recursive) function F, whether there is an decision algorithm A > so the answer to the halting problem of F is trivially yes. The answer is "yes, there is a decision algorithm"? What would that decision algorithm be for this particular function (odd_perfect_number)? And what is its answer?
  - dzsekijo 6y ago
    > The answer is "yes, there is a decision algorithm"? Indeed. > What would that decision algorithm be for this particular function (odd_perfect_number)? Either of () => True or () => False where '()' represents the empty input. > And what is its answer? I'd be a Fields medal candidate if I knew ;)

cortesoft 6y ago

If it definitely exists, don't we then know that this program will definitely halt?

garganzol 6y ago
Only from algebraic and philosophical standpoints. This knowledge is not 100% precise unless a specific number is found.
- groby_b 6y ago
  Nobody cares about the halting problem from a specific standpoint. If it's algebraically guaranteed to halt, it halts. When it halts is entirely meaningless for purposes of the halting problem. But the thing is, it isn't algebraically guaranteed either - we still don't know if an odd perfect number exists. (I'm not sure where the "Definitely. Somewhere in 10^300 range." is coming from. There's nothing definite about the existence, only constraints that need to be satisfied if it exists)
  - cortesoft 6y ago
    In fairness, though, the halting problem doesn't care if you can predict if SOME programs halt... you have to predict if ALL programs halt.
    - groby_b 6y ago
      There's that, too. (Well, we don't have to predict anything. We have to show that halting or not is a decidable condition, and we've shown it isn't. Even if we had shown it was decidable, there still might be programs where we practically can't figure out it halts. So is the beauty of math - it gives us the gestalt of the world without caring about the world :)
  - ProblemFactory 6y ago
    > Nobody cares about the halting problem from a specific standpoint. If it's algebraically guaranteed to halt, it halts. When it halts is entirely meaningless for purposes of the halting problem. Halting problem from a specific standpoint is a popular area of research. Microsoft Research in particular has been active in this area, and Windows device drivers and other kernel event handlers are analyzed to prove that they will halt in a reasonable amount of time to avoid locking up the OS. https://www.microsoft.com/en-us/research/publication/t2-temporal-property-verification/ https://www.microsoft.com/en-us/research/publication/t2-temp...
- greydius 6y ago
  If you've prove a finite upper bound,then you've proven the program will halt. You don't need to know what the exact number is.
  - garganzol 6y ago
    The trick with boundaries does not stand true for evasive predicates on unbounded data. Please note that suggested odd perfect number search algorithm in Python uses an evasive predicate on a big integer which is unbounded. This means that a typical tracer (or verifier in Turing terms) won't be able to infer the upper bound for the given example.

cortesoft 6y ago

The best way the halting problem was explained to me was to think of it like this: imagine you write your perfect halting detection program. It reads in the contents of some program, and returns true if it halts or false if it doesn't. Now, all I have to do is write a program that includes an embedded version of your program. My program reads in the contents of itself and passes it to the embedded program. Now, all my program has to do is take the output of the embedded halt checker, and do the opposite; if the halt checker says the program halts, just keep looping. If it says I don't halt, exit immediately. Now, you might think this is cheating, because it is using your own program against you. However, this is at the core of the problem; it has to work for ALL programs, even ones written with knowledge of your program.

galaxyLogic 6y ago
Doesn't this assume that your program can reliably access it's own source-code? Can it? It can of course read some file containing some source-code. But assume it accesses some file which contains the source-code of some other program, then wouldn't your logic still hold the same, since from the point of your program it is simply reading some file?
- cortesoft 6y ago
  Even if it can't access its source code, you can... you know what the code is
- pjc50 6y ago
  Doesn't matter. Doesn't have to be the executing source, can work with compiled representations; the original Turing paper "compiles" every program to a single giant integer.
- kazinator 6y ago
  No, it has nothing to do with source code. The halting verifier program V never accesses itself. It takes two parameters: a program to check for halting (P) and an input to the program (I). It's job is to test whether P(I) (the program applied to the input) will halt. To trick the halting verifier V we construct a diabolic P like this: program P(I) { if (V(I, I) == YES) { // if Verifier says I(I) halts inifinite_loop(); // ... then do *not* halt } else { halt(); // ... otherwise halt } } Like V, P is a special program that takes a program as input. It then asks the verifier: if the input program is given itself as input, does it halt? And then it behaves in the opposite manner: if the verifier says that I(I) halts, then P deliberately infinite-loops. Otherwise P halts. Given that P, we ask the verifier the devastating question: V(P, P). Does P halt if given itself as input; does P(P) halt? V cannot decide. Note that if we consider P(P), then it means that in the above program, the input parameter I becomes P itself: I = P. And so the V(I, I) == YES expression is actually testing V(P, P) == YES. But V(P, P) is the devastating question itself! If V(P, P) yields YES (P(P) halts) P goes into an infinite loop (P(P) in fact fails to halt), and so V has calculated the wrong answer: the actual behavior of P(P) contradicts the YES answer from V(P, P), rendering V incorrect. The same problem occurs if V(P, P) yields NO. Note that P contains no self refererence. The fact that P is applied to itself as P(P) doesn't come from P; it comes from the way P is used. P is used that way when we ask the verifier V(P, P). The verifier itself is checking what happens if P is given itself as input. P can happily accept other programs as the input I, programs which are not itself. What P needs is a way to embed V, because it relies on it. The assumption is that whatever halting verifier V someone tries to develop, it has to be public. So that is to say, some CS researcher claims he or she has developed a universal halting verifier algorithm V and they publish it. Then, promptly, their adversary takes the algorithm V and sticks it into their program P(I) as a subroutine, and has an instant test case which defeats V. The tricky thing is not self-reference, but the fact that P contains the verifier and turns it against itself. The self-reference is instigated from the outside by choice of inputs. In other words, the devastating question V(P, P) is what perpetrates the self-reference which breaks V.

saagarjha 6y ago

> Does it exist? Definitely. I am unsure how you reached this conclusion?

deleted 6y ago

[deleted]

jondgoodwin 6y ago

Author here. Cool story about odd perfect examples. That said, my post is not trying to find a way to crack the halting problem, and thereby demonstrate it is not real. Turing wrote a most excellent proof, and I stand by it wholeheartedly. I even cite another famous numeric example of a program we still do not know if it will terminate for all numbers: the Collatz conjecture. Notice my description: "Turing proved that no general algorithm can be formulated that can answer this question across all possible programs." The operative part here is "across ALL possible programs". The proof does stop us from knowing that SOME programs will or will not halt. It only stops us from being able to determine this for EVERY possible program. My post explores a very specific subset of programs that we can prove will terminate, then asks what pattern(s) underlie such programs, and then explores the use of such patterns in a variety of interesting problems. It is this last result that most intrigued me, and caused me to write about it.

jondgoodwin 6y ago
Important mistype. It should read: "The proof does NOT stop us from knowing that SOME programs will or will not halt.
- jpt4 6y ago
  It does however apply to more properties than merely halting: https://en.wikipedia.org/wiki/Rice's_theorem https://en.wikipedia.org/wiki/Rice's_theorem
- jpt4 6y ago
  You may also be interested in Willard's Self-Verifying Theories: https://en.wikipedia.org/wiki/Self-verifying_theories https://en.wikipedia.org/wiki/Self-verifying_theories
j-pb 6y ago
A bit tangential, but turings proof only works with some very strict assumptions. - Clasical logic as the foundation for math. - Proofs by contradiction work. - That the church turing thesis holds. I guess these are kinda two sides of the same coin. But still worth noting.

froh 6y ago

Interesting. Nitpick: Odd perfect numbers are no more in the 10^300 range but nowl provably beyond 10^1500. The Wikipedia links to a math paper to that extend.

dzsekijo 6y ago

Sorry to say, this example has nothing to do with the halting problem. Rather, I would say, it's a reformulation of a(n unsolved) mathematical problem to the question whether a certain function halts on a certain input (being "no input", as the function is nullary). Or, if you insist, we can regard it as a trivial instance of the halting problem. An instance of the halting problem asks, given (a partial recursive) function F, whether there is an decision algorithm A (aka. Boolean valued algorithm) on the universe of inputs U of F that calculates the domain of F (those inputs where F takes a value, ie. halts; ie, A(x) <=> F halts on x, where x in U). For any finite subset S = {s_1, ..., s_n} of U, there is a trivial decision algorithm on U that calculates S: def A_S(x): for s in (s_1, ..., s_n): if x == s: return True return False Therefore if the domain D of F is finite, the answer to the halting problem of F is trivially yes: A_D is a decision algorithm for F. (This has noting to do with the question whether we know D or not!) If U is finite, then D is finite, so the answer to the halting problem of F is trivially yes. If F is a thunk (nullary function), then U is finite, ie. the singleton set of "no input", so the answer to the halting problem of F is trivially yes. odd_perfect_number is a thunk.

tom_mellior 6y ago
> An instance of the halting problem asks, given (a partial recursive) function F, whether there is an decision algorithm A > so the answer to the halting problem of F is trivially yes. The answer is "yes, there is a decision algorithm"? What would that decision algorithm be for this particular function (odd_perfect_number)? And what is its answer?
- dzsekijo 6y ago
  > The answer is "yes, there is a decision algorithm"? Indeed. > What would that decision algorithm be for this particular function (odd_perfect_number)? Either of () => True or () => False where '()' represents the empty input. > And what is its answer? I'd be a Fields medal candidate if I knew ;)