Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In short, my question is:

What is the shortest computer program for which it is not known whether or not the program halts?

Of course, this depends on the description language; I also have the following vague question:

To what extent does this depend on the description language?

Here's my motivation, which I am sure is known but I think is a particularly striking possibility for an application to mathematics:

Let $P(n)$ be a statement about the natural numbers such that there exists a Turing machine $T$ which can decide whether $P(n)$ is true or false. (That is, this Turing machine halts on every natural number $n$, printing "True" if $P(n)$ is true and "False" otherwise.) Then the smallest $n$ such that $P(n)$ is false has low Kolmogorov complexity, as it will be printed by a program that tests $P(1)$, then $P(2)$, and so on until it reaches $n$ with $P(n)$ false, and prints this $n$. Thus the Kolmogorov complexity of the smallest counterexample to $P$ is bounded above by $|T|+c$ for some (effective) constant $c$.

Let $L$ be the length of the shortest computer program for which the halting problem is not known. Then if $|T|+c < L$, we may prove the statement $\forall n, P(n)$ simply by executing all halting programs of length less than or equal to $|T|+c$, and running $T$ on their output. If $T$ outputs "True" for these finitely many numbers, then $P$ is true.

Of course, the Halting problem places limits on the power of this method.

Essentially, this question boils down to: What is the most succinctly stateable open conjecture?

EDIT: By the way, an amazing implication of the argument I give is that to prove any theorem about the natural numbers, it suffices to prove it for finitely many values (those with low Kolmogorov complexity). However, because of the Halting problem it is impossible to know which values! If anyone knows a reference for this sort of thing I would also appreciate that.

share|improve this question
1  
My money is on tag systems: en.wikipedia.org/wiki/Tag_system#The_2-tag_halting_problem –  Steve Huntsman Jun 29 '10 at 18:37
    
Note here that the "length of the program" includes the input---so this is a little less clear. –  Daniel Litt Jun 29 '10 at 18:46
    
Maybe one can also find some short λ-terms having neither a known normal form, nor a proof of non-existence of it; unfortunately, I can’t find anything on the topic. –  Antonio E. Porreca Jun 29 '10 at 19:19
    
"By the way, an amazing implication of the argument I give is that to prove any theorem about the natural numbers, it suffices to prove it for finitely many values..." A proof would require you prove P(n) for those finitely many n and to prove that those values are sufficient. This would prove the halting or non-halting of the TM that tests P(1), P(2)... You could turn this around to solve the halting problem. Given a TM M, define P(n) = false iff M halts with $n$ on its tape. Proving P(n)=true for all n proves that M does not halt. Finding an n so that P(n)=false proves that M halts –  Travis Service Jun 29 '10 at 22:01
    
@Travis: Which is why I wrote "However, because of the Halting problem it is impossible to know which values! If anyone knows a reference for this sort of thing I would also appreciate that." –  Daniel Litt Jun 29 '10 at 22:32
show 3 more comments

9 Answers 9

up vote 42 down vote accepted

There is a 5-state, 2-symbol Turing machine for which it is not known whether it halts. See http://en.wikipedia.org/wiki/Busy_beaver.

share|improve this answer
    
This does seem like a good contender. Is the halting status of every 4-state, 2-symbol machine known? –  Daniel Litt Jun 29 '10 at 18:57
1  
Daniel: yes, since S(n) is known for n = 4. –  Antonio E. Porreca Jun 29 '10 at 19:04
    
Ah, fair enough. That answers original question to my satisfaction, though if someone wants to address the "descriptive language" question and the reference request, that would also be great. –  Daniel Litt Jun 29 '10 at 19:05
add comment

You may find my blog post "Are small sentences of Peano arithmetic decidable?" relevant. In summary, John Langford and I investigated short sentences of Peano arithmetic. We enumerated them all (actually, our laptops did) and eliminated those that could be recognized as decidable. It quickly turned out that Diophantine equations were difficult to recognize as decidable. Among those we found two that gave a professional number theorist something to munch on (all quantifiers range over $\mathbb{N}$): $$\exists a, b, c . \; a^2 - 2 = (a + b) b c$$ and $$\exists a, b, c . \; a^2 + a - 1 = (a + b) b c.$$

The shortest unsolved sentence I am aware of is ($S$ is the successor function) $$\forall a \exists b \forall c, d . \; (a+b)(a+b) \neq S(S( (S(S c)) \cdot (S(S d)))).$$ It says (more or less) that there are infinitely many primes of the form $x^2 - 2$.

What I found most surprising was that mixed quantifiers were easier than just straight universal or existential statements. It seems that with very few symbols to spare for the matrix, you cannot produce an interesting mixed-quantifier sentence.

share|improve this answer
1  
+1 I was wondering if someone would answer along these lines! Based on your blog post, I infer that you have not actually enumerated and solved all the statements shorter than the one you give; is that the case? –  Daniel Litt Jul 3 '10 at 7:15
    
This was some time ago. If I remember correctly we enumerated all universal statements up to 15 symbols where we took inequality is a basic symbol (and did not use negation). Approximately 3000 of those could not be recognized as decidable by our heuristics. Practically all of them were Diophantine equations (actually their negations), except possibly for a couple of systems of equations. We also investigated mixed-quantifier sentences and I think we got up to something like 10 and never found an interesting one. –  Andrej Bauer Jul 3 '10 at 14:17
    
Is the statement ∃a,b,c.a^2−2=(a+b)bc true? –  Thomas Jan 17 at 23:16
add comment

It's quite possible that the Collatz conjecture provides an answer. Apply this function repeatedly. The conjecture is that this process will eventually reach the number 1, regardless of which positive integer is chosen initially.

alt text

Not sure how many lines of code this would be. Probably 2 in Haskell.

share|improve this answer
6  
It's possible; this isn't a big list question though--I'm not looking for guesses. I'm actually wondering if someone has enumerated all short programs and tried to prove that they halt, with an aim of pursuing the application I describe in the question. –  Daniel Litt Jun 29 '10 at 18:53
2  
@Daniel Litt: regarding that comment, you should look at work such as cs.auckland.ac.nz/~cristian/Calude361_370.pdf . In that paper, the authors compute the first 64 bits of an $\Omega$-number explicitly. Of course these bits are utterly dependent on the choice of a universal prefix-free machine. –  Carl Mummert Jun 29 '10 at 19:48
    
Thanks! Looks good. –  Daniel Litt Jun 29 '10 at 19:49
    
I guess you mean to make the function recursive? f(n) = f(n/2), f(n) = f(3n+1), etc. Also you need the base case. Otherwise this function is easily computable. :-) –  Wilson Jun 29 '10 at 21:16
    
Also, there's the question of how long the bit representation is of the smallest n not known to halt. –  Wilson Jun 29 '10 at 21:17
show 1 more comment

The answer depends utterly and completely on the description language. Rogers called a description language "acceptable" if there is a pair of effective methods, one to convert standard programs to programs in the language D, and one to convert programs in D to standard programs. (More precisely, these description languages are just numberings of the set of partial computable functions.) Now for any program whatsoever, there is an acceptable description language which assigns that program to index 0. So any program you like can be the shortest example, if you pick the right acceptable numbering.

This is the same kind of reason that, for any string of length 2 or more, there is a universal prefix-free machine that makes the string Kolmogorov random, and another universal prefix-free machine that makes the string not Kolmogorov random.

share|improve this answer
    
This is true, but somehow a very naive answer--if we include the length $p$ of a "translator" program into our analysis of the dependence of length on description language, the dependence is a little less arbitrary. That is, any program in language 1 of length $x$ gives a program of length $p+x$ in language $2$. –  Daniel Litt Jun 29 '10 at 19:24
    
To do that, you still must start with a "preferred" description language, and the complexity will depend on which one you think of as preferred. Perhaps the one I prefer assigns some function to index 0, while your preferred one assigns that function only much larger indices. –  Carl Mummert Jun 29 '10 at 19:43
    
Ah sorry I was unclear. I'm not suggesting a definition of complexity that is independent of language--just that the length of "translators" provides a bound on the difference between the two complexities. Essentially, my second question was asking whether there is any less trivial relationship (and aiming towards applications, whether we can pick a language in a tricky way to make the method for proof I suggest at all reasonable). –  Daniel Litt Jun 29 '10 at 19:47
    
I think you will find the paper I posted above interesting. –  Carl Mummert Jun 29 '10 at 19:49
    
Definitely, it looks fantastic. Wish I could accept that comment as an answer as well. –  Daniel Litt Jun 29 '10 at 19:51
add comment

Readers might be interested to know that congruential iterations similar to the Collatz 3n+1 problem were discovered "in the wild" while trying to understand the behavior of various busy beaver candidate machines. Since John Conway has shown that deciding termination of certain classes of such congruential iterations is undecidable, it may be the the boundary of undecidability already lies in one of these open busy beaver congruential iteration problems. For much further discussion and references see my old post on sci.math, 13 Feb 1996, halting is weak? http://groups.google.com/group/comp.lang.scheme/msg/b8c43aee2bc12241
http://google.com/groups?selm=WGD.96Feb13081831%40berne.ai.mit.edu

share|improve this answer
add comment

Regarding to prove any theorem about the natural numbers, it suffices to prove it for finitely many values ... impossible to know which values [where the context explains that the theorem is a universally quantified statement $\forall n\\,P(n)$]: this is trivial, and one value suffices. Namely, define $n_0$ as follows: if the statement is false, let $n_0$ be the smallest counterexample, otherwise let $n_0:=0$. Then the statement holds if and only if $P(n_0)$.

share|improve this answer
    
This is obviously not the intent of my claim; if you can show me a Turing machine which, given $P$, prints a correct (numerical) value of $n_0$, however, I'll be pretty impressed. Of course, such a machine would solve the halting problem. –  Daniel Litt Mar 10 '11 at 16:32
3  
Emil's statement looks to me entirely parallel to the claim in the question. Emil says to check $n_0$ but gives you no clue how to find it. The claim in the question says to check all halting programs up to a certain length but gives you no clue how to determine which programs those are. –  Andreas Blass Mar 10 '11 at 16:44
    
Well this is a bit of a quibble, but my claim is that given a correct value, one can produce a proof--on the other hand, Emil's "value" does not allow one to produce a proof. Instead, it produces something silly like "If there is an odd perfect number, let $x$ be that number; otherwise, let $x$ be a proof that there is no odd perfect number." In any case, I think we all understand each other and pretty much agree that the proof technique I "suggest" is essentially useless. –  Daniel Litt Mar 10 '11 at 17:27
    
@Daniel, If you prove the statement for $n_0$ then by the definition of $n_0$ it would follow for all. –  Kaveh Sep 21 '12 at 21:03
add comment

This doesn't qualify as "shortest" but is my favorite example of why humans can't solve the halting problem:

for all odd numbers $n = 1,3,5,...$

    if $n$ is perfect, halt.

This program halts if and only if there is an odd perfect number. Of course, the query "is $n$ perfect" is not terribly short (but can be computed by adding one more for loop).

share|improve this answer
add comment

this question is apparently closely related to Wolframs research program of determining whether "small" Cellular Automata [CAs][1] are Turing Complete. if the CA is proved Turing Complete then by mapping with Turings halting problem, there exists an input for which termination of the CA cannot be proven. but also determining whether the CA is Turing complete can be very difficult and there are several so-far-indeterminate cases. a case where it succeeded but with a very complex proof is [2], some further details of the dynamics in [4]. see also [5] for a writeup of an ambitious somewhat recent "major attack" on the busy beaver problem that superseded many prior results. and there is also a related long tradition of research for finding small state universal TMs[3,6] probably dating to the ~1960s including results by Marvin Minsky. re Collatz conjecture candidate & a boundary with "nearby" problems similar to Conway-type, see also [7]

[1] Elementary cellular automata, wikipedia

[2] Rule 110, wikipedia

[3] tcs.se, whats the simplest noncontroversial 2 state universal TM

[4] tcs.se initial conditions for rule 110

[5] New-Millenium Attack on the Busy Beaver Problem by Ross et al

[6] The complexity of small universal Turing machines: a survey Woods & Neary

[7] tcs.se, whats the nearest problem to the Collatz conjecture thats been successfully resolved?

share|improve this answer
add comment

The following is based on Waring's Problem:

For all n floor((3/2)^n) + 3^n mod 2^n < 2^n. Kubina has tested this up to 471,600,000.

x = 9; for( y = 4 ; x/y + x%y < y ; y *= 2 ) x *= 3;

Assume that x and y are int's with unlimited size.

Whereas small Turing machines have been exhaustively analysed and, as Richard notes, there is a 5-state 2-symbol TM whose halting is unknown, I have not seen a similar analysis for other models of computation (Register Machines, LOOP programs, C programs). So I propose the above C program (containing 32 symbols) as the shortest whose halting is unknown.

In the program x contains powers of 3 and y contains corresponding powers of 2 (x*=3 multiplies x by 3).

share|improve this answer
    
If this is an answer to the question, "What is the shortest program fro which halting is unknown?" you'll have to flesh it out. If it's not an answer to that question, it doesn't belong here. –  Gerry Myerson Oct 4 '12 at 5:47
3  
Integers in C are always bounded (but the bound depends on the implementation) so this program doesn't work as intended. –  François G. Dorais Oct 4 '12 at 13:47
    
The program seems to be written in a nonstandard version of C in which ints are unbounded. It is reasonable to consider this variant language as a model of computation, and it is reasonable to ask about short programs in this language, but it seems unreasonable to claim that your answer satisfies the constraints of working in C. –  S. Carnahan Oct 5 '12 at 2:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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