9
1
To solve the Halting Problem you are given a description of a program, and must determine whether or not it will ever finish. You can never do this for all programs. Yet for programs like (in brainf***):
>
It obviously will halt, and for programs like:
+[]
It obviously will not. Your challenge is to "solve" the halting problem for as many programs as possible. These programs will not use .
or ,
, and will not have input or output. You will be given a description of the program and must output either "Halts", "Does not halt", or "Unknown". When your program outputs "Halts" or "Does not halt", you have solved the input program. Here are some requirements.
- It must solve at least an infinite amount of programs.
- For every program it solves, its solution must be correct.
- You may only output 1 of the 3 above choices.
- You may assume that the running computer has infinite time and memory, so XKCD 1266 would not work (the tape is unlimited).
- No external resources.
- You may not use a programming language that can actually solve the halting problem.
You may have a non-code-golfed side program that takes a string that is a program, and generates some sort of abstract syntax tree of it if you like. Note, that isn't really scoring per se, but how to determine if one program beats another.
- If program A solves an infinite number of programs that B doesn't, but B only solves finite or no programs that A solves, A automatically wins.
- Otherwise, the program with the fewest characters wins. Do not count white space or comments, so do not obfuscate your code.
Tip: Timers won't work. You see, for any time T and given machine, there is an N, such that all programs longer than that have to take more than T time. This means that a timer can only achieve the solution of a finite number of programs, and, as you can see above, solving a finite number of programs doesn't help.
What if two submissions
a
andb
can solve programs in setA
andB
respectively, and bothA\B
andB\A
are infinite? The shorter program wins? – user202729 – 2018-05-23T07:56:42.803Can the submission itself not halt for some inputs? – user202729 – 2018-05-23T07:59:30.573
@user202729 nope – PyRulez – 2018-05-23T11:33:59.810
@user202729 exactly – PyRulez – 2018-05-23T11:34:24.090
Then which one win in that case? – user202729 – 2018-05-23T11:45:52.330
@user202729 the shorter one – PyRulez – 2018-05-23T12:09:30.840
3I don't think the scoring system will work. Given any solution, it is easy to construct a better one as follows: Find any program P on which the solution S outputs "Unknown", create a new solution which outputs the correct answer on input P, the same answer on P with any number of
>
s added to the end (since these halt iff P halts), and outputs S's answer on all other inputs. This new solution solves infinitely more problems than S. – cardboard_box – 2014-03-08T17:03:52.033These made not add any solutions though. For example, the original P could just say "if the last thing is
>
, ignore it." Then your thing would be redundant. – PyRulez – 2014-03-08T17:06:26.750Right, so first create a solution S' which answers the same as S but ignores
>
s after the end of the program, then find a program P on which S' answers "Unknown", then create a new solution that answers correctly on P with>
s appended and gives the answer of S' otherwise. Since S' ignores>
s then P with any number of>
s appended will also not be solved by S'. – cardboard_box – 2014-03-08T17:12:46.627I am having trouble following. Reword as
P(x)
meaning the solution (or nonsolution) of x according to P. – PyRulez – 2014-03-08T17:17:02.307Never mind, I just realized I was assuming that appending
>
s wouldn't make a solution change from "Unknown" to the correct answer but this is not necessarily the case. – cardboard_box – 2014-03-08T17:26:07.970I don't understand requirement 6. I also don't understand why you say that the halting program can't be solved for all programs given that the reference implementation has a very finite state space. – Peter Taylor – 2014-03-08T17:29:53.233
3"At least an infinite amount of programs"? Is there a bonus for solving more? ;-) – Jonathan Van Matre – 2014-03-08T17:44:17.290
What exactly does rule #2 mean? – Kendall Frey – 2014-03-08T17:52:50.363
@PeterTaylor Clarified – PyRulez – 2014-03-08T17:54:03.263
@KendallFrey Spell check error. Corrected. – PyRulez – 2014-03-08T17:54:27.390
Is there a limit on the number of data cells in the BF machine (bounded) or is it unlimited? – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ – 2014-03-08T18:05:38.463
It is unlimited. – PyRulez – 2014-03-08T18:15:47.613
1Since you're apparently not following the reference implementation, you should probably clarify all of the other implementation differences: cell size, behaviour on underflow and overflow, whether the tape is infinite in both directions or only one, and if only one what happens when you try to move past it. It's not the most tightly specified language... – Peter Taylor – 2014-03-08T18:40:59.667
You should change the rules so that only the number of correct "doesn't halt" answers are counted. Identifying infinitely numbers of programs that do halt is easy - all you have to do is run them for a long time and see if they halt. It's the ones that don't that make the problem hard. – Nathaniel – 2014-05-04T02:35:56.453