-2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Poor Turing.... \$\endgroup\$ – kirbyfan64sos Oct 9 '15 at 22:48
  • 1
    \$\begingroup\$ How would your H recognize an X? \$\endgroup\$ – LegionMammal978 Oct 10 '15 at 18:58
  • 1
    \$\begingroup\$ @LegionMammal978 You only have to detect one X of your choosing. (I think it may actually be impossible to detect X programs in general.) \$\endgroup\$ – PyRulez Oct 10 '15 at 19:01
  • 1
    \$\begingroup\$ 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". \$\endgroup\$ – lirtosiast Oct 10 '15 at 19:06
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – lirtosiast Oct 10 '15 at 19:16
1
\$\begingroup\$

Mathematica, 140 138 127 bytes

H=(While[#==#2[[1]]=="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"]&
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – lirtosiast Oct 10 '15 at 19:21
  • \$\begingroup\$ 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. \$\endgroup\$ – PyRulez Oct 10 '15 at 21:33
  • \$\begingroup\$ @LegionMammal978 That's to determine if it halts. It doesn't tell you if it doesn't halt. \$\endgroup\$ – PyRulez Oct 11 '15 at 12:52
  • \$\begingroup\$ @LegionMammal978 Analyze the source. Figure out an infinite number of cases, then the program gives up. \$\endgroup\$ – PyRulez Oct 11 '15 at 13:02
  • \$\begingroup\$ @LegionMammal978 Only one X, but a smallish infinity of other infinite loops (not all of them, just an infinite number of them). \$\endgroup\$ – PyRulez Oct 11 '15 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.