Here goes a quick proof by Alan Turing that there is no program
H that can solve the halting problem. If there was, you could make a program
X such that
X(n) = if H(n,n) == Halt then output X(n) else output ":-)". What is the value of
Your job is to make a partial halting solver, such that when some
X of your choice is inputted, your program will output "Curse you Turing!!!" repeatedly.
Specifically, you will make two programs in the same programming language. One will be
H, the partial halting solver. Given a program
P (in the same programming language) and an input, H will:
- output "halts" if
- output "no halts" if
X), output "Curse you Turing!!!" infinitely, on different lines.
Hcan't figure out if
Phalts, go into an infinite loop without output.
X, will be given an input
n, and then it will check
H(n,n). If it outputs "not halts", it will terminate at some point. For any other result of
H(n,n), it will go into an infinite loop. The output of
X is unimportant.
X will not have access to external resources. Specifically, that means that there is a mutual-quine-aspect to this problem.
As to how hard
H has to try to figure out whether a program halts:
- Once it determines that its input isn't
X, it will run the program with the input for 10 seconds. If it terminates (either correctly or with error) it will output "halts".
- You must identify an infinite number of "no halts" programs.
Oh, and this may be go without saying, but the programming language needs to be Turing complete (I knew you were thinking of an esoteric language without infinite loops. Sorry.) (That said, Turing complete subsets of languages are also okay.)
Your score is the number of bytes in
H. Least number of bytes wins!
- -50 bytes: If
Hcaptures output from its input program, and reoutputs it but with "PROGRAM OUTPUT: " in front of every line. (This is only done when
Hruns the program to test it.)
- -20 bytes: If
Houtputs "halts" based on criteria other than time as well.
Try and find a fun combination of
X calls to put together to make it interesting (like
H(H,(X,X)) or even more crazy stuff.)