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:
x2 = H'(x1) -> H(x1) -> false -> halt
-> program x2 would haltx3 = H'(x2) -> H(x2) -> true -> loop
… program x3 would loopIf 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)
?
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP