1

I've looked up a lot proofs for the halting problem (that are basic enough that I can understand what they are trying say ^^) but for all of them I don't get their last step right before they pull the conclusion out of a magic hat.

Assume we have a function H(x) -> bool that can determine if a program x halts or not. We also assume that H(x) always halts (we ignore invalid programs/inputs for now) and is quite fast O(n) or even O(1). Keypoint is that H(x) can decide if it halts without executing the code from the input.

H(x) can process any program that is self contained, meaning that the program x must not have any inputs or outputs - we are just interested if it halts or not. The input constraint is important, because if a program halts or not may of course depend on the input. If you have a program that requires inputs, like X(a, b), you must harcode them and create a self contained program (x = X(4,2)). This way all programs (even ones that require input) can be reduced to a program without inputs.

To get things stated we have two programs

  • x1 ... A program with an endless loop (never halts)
  • x2 ... A program that halts (for example a basic hello world program)

All proofs I found construct a new machine based on H(x).

H'(x) = match H(x){
    true -> loop forever
    false -> halt
}

And now they try to pass H'(x) into H(x) and somehow come to the conclusion H(x) is impossible. But limited by our constraint that it's invalid to pass H'(x) directly into H (because it requires inputs) we have to construct a self contained program.

But that's actually not a problem because there are only two cases:

  • We input a program into H' that loops
    x2 = H'(x1) -> H(x1) -> false -> halt -> program x2 would halt
  • We input a program into H' that halts
    x3 = H'(x2) -> H(x2) -> true -> loop ... program x3 would loop

If we would pass those new programs (based on H) into H it would give us the correct results H(x2) -> true and H(x3) -> false and I don't see the contradiction here.

My guess is that I missed something or all proofs that are basic enough that I can understand them are simplified down to the point where they no longer work.

So my question is what self contained program (without inputs) would lead to a contradiction if feed to H(x) or H'(x)?

Improve this question
5

1 Answer 1

Reset to default
3

Your problems are that you've added an input to H', when H' shouldn't have and doesn't need any inputs and you missed the point that H' specifically passes itself to H, not just any arbitrary function. It should look more like this:

H'() = match H(H'){
    true -> loop forever
    false -> halt
}

Thus, H' does the opposite of what H says H' does.

Improve this answer
7
  • But H' is a function which means that H can't have enough information to decide it. It's like asking you if while(some_secret_input){} halts without telling you the input. There is no way you could know. Passing H' (a function that needs an input) into H without telling it the input can't work.
    – wischi
    Commented Jul 22, 2020 at 16:50
  • @wischi H' shouldn't have and doesn't need any inputs
    – 8bittree
    Commented Jul 22, 2020 at 16:51
  • @wischi Alternatively, if you really want to give H' an input as in your question, you can. Then, the contradictory input parameter is H' itself. It's not a secret.
    – 8bittree
    Commented Jul 22, 2020 at 16:57
  • Oh I think it slowly dawns on me, thank you. But I'm still not sure what the implications are, because your suggestion to keep the parameter and pass in H' wouldn't work because you can't pass H' because it itself would need a parameter to be self-contained.
    – wischi
    Commented Jul 22, 2020 at 17:03
  • I think the point that H' doesn't need/have any parameters put me on the right track but I'm not sure how someone would put the code of H' (for example as a string) inside the definition without referencing an external function (itself for example). I put together a short C# program and have no idea (working under the assumption that DoesHalt is implemented) how I would create a contradiction: gist.github.com/wischi-chr/7ff2731300d187cada803a38efb3a079 My guess is that it would have to be some kind of quine?
    – wischi
    Commented Jul 22, 2020 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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