43
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ My money is on tag systems: en.wikipedia.org/wiki/Tag_system#The_2-tag_halting_problem $\endgroup$
    – Steve Huntsman
    Commented Jun 29, 2010 at 18:37
  • $\begingroup$ Note here that the "length of the program" includes the input---so this is a little less clear. $\endgroup$
    – Daniel Litt
    Commented Jun 29, 2010 at 18:46
  • $\begingroup$ 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. $\endgroup$
    – Antonio E. Porreca
    Commented Jun 29, 2010 at 19:19
  • 3
    $\begingroup$ "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 $\endgroup$
    – Travis Service
    Commented Jun 29, 2010 at 22:01
  • 1
    $\begingroup$ @DanielLitt Keep iterating through evens; if for any one; two prime summands not found halt $\endgroup$
    – ARi
    Commented Oct 3, 2013 at 15:05

10 Answers 10

Reset to default
60
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This does seem like a good contender. Is the halting status of every 4-state, 2-symbol machine known? $\endgroup$
    – Daniel Litt
    Commented Jun 29, 2010 at 18:57
  • 2
    $\begingroup$ Daniel: yes, since S(n) is known for n = 4. $\endgroup$
    – Antonio E. Porreca
    Commented Jun 29, 2010 at 19:04
  • $\begingroup$ 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. $\endgroup$
    – Daniel Litt
    Commented Jun 29, 2010 at 19:05
  • 1
    $\begingroup$ The halting status of all $5$-state Turing machines is now known, after having been resolved by the bbchallenge project earlier this month. $\endgroup$
    – C7X
    Commented Jul 21 at 11:51
51
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ +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? $\endgroup$
    – Daniel Litt
    Commented Jul 3, 2010 at 7:15
  • $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Commented Jul 3, 2010 at 14:17
  • 9
    $\begingroup$ Is the statement ∃a,b,c.a^2−2=(a+b)bc true? $\endgroup$
    – Thomas
    Commented Jan 17, 2014 at 23:16
  • 2
    $\begingroup$ No, there are no natural numbers $a$, $b$ and $c$ for which $(a^{2} - 2) = (a+b)bc$. If one assumes that $a$ is minimal for which there exist such $b$ and $c$, then one can let $a_{1} = a - cb$, $b_{1} = (c+1)b - a$ and $c_{1} = c$. This triple also satisfies $(a_{1}^{2} - 2) = (a_{1}+b_{1})b_{1} c_{1}$. This gives a contradiction. (This is really a Vieta jumping argument like is used in the fairly well-known 1988 IMO problem. See here.) $\endgroup$
    – Jeremy Rouse
    Commented May 10, 2020 at 16:34
7
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Daniel Litt
    Commented Mar 10, 2011 at 16:32
  • 5
    $\begingroup$ 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. $\endgroup$
    – Andreas Blass
    Commented Mar 10, 2011 at 16:44
  • $\begingroup$ 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. $\endgroup$
    – Daniel Litt
    Commented Mar 10, 2011 at 17:27
  • 1
    $\begingroup$ @Daniel, If you prove the statement for $n_0$ then by the definition of $n_0$ it would follow for all. $\endgroup$
    – Kaveh
    Commented Sep 21, 2012 at 21:03
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 7
    $\begingroup$ 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. $\endgroup$
    – Daniel Litt
    Commented Jun 29, 2010 at 18:53
  • 2
    $\begingroup$ @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. $\endgroup$
    – Carl Mummert
    Commented Jun 29, 2010 at 19:48
  • 1
    $\begingroup$ 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. :-) $\endgroup$
    – Wilson
    Commented Jun 29, 2010 at 21:16
  • $\begingroup$ Also, there's the question of how long the bit representation is of the smallest n not known to halt. $\endgroup$
    – Wilson
    Commented Jun 29, 2010 at 21:17
  • $\begingroup$ You are right. I mean the recursive function. $\endgroup$
    – supercooldave
    Commented Jun 29, 2010 at 21:31
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$
    – Daniel Litt
    Commented Jun 29, 2010 at 19:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Carl Mummert
    Commented Jun 29, 2010 at 19:43
  • $\begingroup$ 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). $\endgroup$
    – Daniel Litt
    Commented Jun 29, 2010 at 19:47
  • $\begingroup$ I think you will find the paper I posted above interesting. $\endgroup$
    – Carl Mummert
    Commented Jun 29, 2010 at 19:49
  • $\begingroup$ Definitely, it looks fantastic. Wish I could accept that comment as an answer as well. $\endgroup$
    – Daniel Litt
    Commented Jun 29, 2010 at 19:51
5
$\begingroup$

May I suggest the use of Binary Lambda Calculus [1] for writing programs and measuring their size in bits?

There are many BLC programs of only a few dozen bits, comparable in complexity to 5 state TMs that need nearly 50 bits to describe, whose halting behavior is unknown.

Beyond that, there are programs like this 215 bit one for computing Laver tables [2], whose halting behavior is related to existence of large cardinals. A counterexample to Goldbach's conjecture can be found with a 267 bit program.

I decided to pose a question on mathoverflow [3] addressing the specific form of the question.

[1] https://tromp.github.io/cl/Binary_lambda_calculus.html

[2] https://codegolf.stackexchange.com/questions/79620/laver-table-computations-and-an-algorithm-that-is-not-known-to-terminate-in-zfc

[3] What's the smallest lambda calculus term not known to have a normal form?

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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?

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Integers in C are always bounded (but the bound depends on the implementation) so this program doesn't work as intended. $\endgroup$
    – François G. Dorais
    Commented Oct 4, 2012 at 13:47
  • 2
    $\begingroup$ 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. $\endgroup$
    – S. Carnahan ♦
    Commented Oct 5, 2012 at 2:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .