# Curse you Turing!!! Make a partial halting solver that yells at Turing when he tries to break it

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 H(X,X)?

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 P halts
• output "no halts" if P doesn't halt
• If P is program X (with input X), output "Curse you Turing!!!" infinitely, on different lines.
• If H isn't X, and H can't figure out if P halts, go into an infinite loop without output.

Program 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.

H and 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 and 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!

Bonuses:

• -50 bytes: If H captures output from its input program, and reoutputs it but with "PROGRAM OUTPUT: " in front of every line. (This is only done when H runs the program to test it.)
• -20 bytes: If H outputs "halts" based on criteria other than time as well.

Try and find a fun combination of H and X calls to put together to make it interesting (like H(H,(X,X)) or even more crazy stuff.)

• Poor Turing.... Oct 9 '15 at 22:48
• How would your H recognize an X? Oct 10 '15 at 18:58
• @LegionMammal978 You only have to detect one X of your choosing. (I think it may actually be impossible to detect X programs in general.) Oct 10 '15 at 19:01
• The challenge is mathematical only in genre—its only link to math is that the Halting problem is a mathematical topic. Entries will need to use quine techniques, but solve no math problems. I quote from the tag wiki: "Challenges relating to or in some way involving mathematics; that is, solving a math problem is needed to come up with a solution, or the solution is a program that solves a math problem, or the program generates math problems, etc." It mentions nothing about genre. We didn't tag Minimal NetHack "game". Oct 10 '15 at 19:06
• Yes, but again only in genre. A sufficiently talented programmer who knows nothing of math, computer-scientific or otherwise, could solve the challenge as well as Turing himself. The solutions do not "partially [solve] the halting problem" in a mathematical sense; they simply determine whether the input is its source code, or if it halts in less than 10 seconds. Oct 10 '15 at 19:16

# Mathematica, 140138 127 bytes

H=(While[#==#2[]=="While[#~H~{#}==\"halts\"]&",Print@"Curse you Turing!!!"];TimeConstrained[#=="#&"||ToExpression@#@@#2;"halts",10,"no halts"])&


Defines a function H that takes a function string and argument list as arguments. This also receives the -20 bonus, with the extra criteria being that if the program is #&, then it halts. This is to show that it is flawed. Here is the X:

While[#~H~{#}=="halts"]&

• You should test your own submissions, but I'll fire up my copy of Mathematica, try to find out how it works, and look at this. Oct 10 '15 at 19:21
• For which programs does it output "no halts"? It looks like it outputs "no halts" for programs over 10 seconds. They could still halt, its just unknown. Oct 10 '15 at 21:33
• @LegionMammal978 That's to determine if it halts. It doesn't tell you if it doesn't halt. Oct 11 '15 at 12:52
• @LegionMammal978 Analyze the source. Figure out an infinite number of cases, then the program gives up. Oct 11 '15 at 13:02
• @LegionMammal978 Only one X, but a smallish infinity of other infinite loops (not all of them, just an infinite number of them). Oct 11 '15 at 13:04