Does the stopping problem mean programs cannot check other programs?
I'm taking a theoretical CS class and we just discussed the halting problem. In my opinion, the reason the problem cannot be resolved is because if there is a Halt program that tells us if the program stops and you write another program. The proof is that
function Proof (program, input)
if (Halt(program, input)) loop infinitely;
else return 1
For me, the crux of the problem is that the if condition for the program is infinitely looping, which is a failure condition for Halt.
This is the part I'm not sure about:
Say you have a program to check if another program returns the number 4 on a specific input. Let me call this program FourCheck. Then we could write another ProofFour program such that
ProofFour(program, input)
if(FourCheck(program, input) return 5;
else return 4;
In this case, we could call ProofFour (ProofFour, input). If FourCheck () returns true, ProofFour returns 5, which makes FourCheck ()'s output incorrect. If FourCheck returns false, then ProofFour returns 4, which makes the output of FourCheck () incorrect.
Hence, it would be correct to assume that you essentially did not have a program to test other programs, because you could always create a program similar to Proof () and ProofFour () that essentially inverts the output of your check program.
source to share
ProofFour(program, input)
if(FourCheck(program, input)) return 5;
else return 4;
With the above program, your call is ProofFour(ProofFour,input)
ill-formed: the first Prooffour
is fine, since it takes a program and input as its input, and the second Prooffour
must have two arguments.This means you need to supply a paired input for the second Prooffour
, since this is: ProofFour(ProofFour,(someprog, input))
When you are using this well-defined form, it is difficult (if not impossible) to explain why it is not possible to create a FourCheck ().
Now I have changed it a bit:
ProofFour(input)
if(FourCheck(ProofFour, input)) return 5;
else return 4;
It is a well-defined shape. ProofFour in a program is just a pointer to the program text. It is now clear that Fourcheck cannot test the ProofFour program.
source to share