TransWikia.com

How does the classic proof for the halting problem work?

Software Engineering Asked by wischi on November 28, 2021

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)?

One Answer

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.

Answered by 8bittree on November 28, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP