The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. What are the simplest (smallest) known examples of such programs?
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ similar question What is the smallest Turing machine where it is unknown if it halts or not? / Theoretical Computer Science $\endgroup$– vznCommented Jul 30, 2015 at 15:47
-
$\begingroup$ More precise problem statement in terms of number of states of a Turing machine: cs.stackexchange.com/questions/59344/… $\endgroup$– Ciro Santilli OurBigBook.comCommented Sep 17, 2023 at 21:16
-
$\begingroup$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Computer Science Meta, or in Computer Science Chat. Comments continuing discussion may be removed. $\endgroup$– D.W. ♦Commented Apr 28 at 23:39
-
$\begingroup$ This question is similar to: What are very short programs with unknown halting status?. If you believe it’s different, please edit the question, make it clear how it’s different and/or how the answers on that question are not helpful for your problem. $\endgroup$– codyCommented Jul 11 at 21:39
Add a comment
|
9 Answers
$\begingroup$
$\endgroup$
4
Take any open problem in Number Theory and convert it into a question of whether a given program terminates. E.g. One example that works for the twin prime conjecture is:
f(x):
while gcd(x^2 - 1, sqrt(x+1)#) != 1:
x += 1
return x
Clearly passing in $x \in \Bbb{N}$ will return the next twin prime average that is $\geq x$. We can't seem to prove that this algorithm will always terminate (as that immediately implies an infinitude of twin primes).
We can refactor this into a more general question. Does the following program terminate for any 3 natural numbers $x,y,z$?
g(x,y,z):
while gcd(xy,z) != 1:
z *= x
x += 1
y += 1
If you can prove that this always terminates, then passing in certain values for $x,y,z$ similar to the first function's variable values, then you've also proven twin primes.
It is hopeless!
-
2$\begingroup$ It's worth noting that not every problem can be so translated - only those which are expressible as a $\Pi^0_2$ statement. $\endgroup$ Commented Apr 29 at 1:36
-
$\begingroup$ By the way, the # means "primorial". But you could also use $(x-2)!$ or $(x-2)\#$. By Sieve-of-Eratosthenes there's a huge leeway of selections for this number. $\endgroup$ Commented Apr 29 at 19:46
-
$\begingroup$ @MaiaVictor This is the quintessential article I found on modern Termination analysis and has references to all the standard literature on the subject matter they mention: blogs.evergreen.edu/sosw/files/2014/03/wk2Cook.pdf Makes me wonder if any of the techniques can be applied to these Twin Prime termination questions. Might be a good question for someone to research. $\endgroup$ Commented Apr 29 at 19:48
-
$\begingroup$ Also note that if you expand the $\gcd$ in place you get the full arithmetic-only operational program but it's with two while loops, one nested in the other. See the Wikipedia Euclidean algorithm article for ways of coding $\gcd$ and one of them merely involves some $\lt$ comparisons and subtraction. Similar to the simplified algorithm the linked article analyzes. $\endgroup$ Commented Apr 29 at 19:54
$\begingroup$
$\endgroup$
6
A pretty simple example could be a program testing the Collatz conjecture:
$$ f(n) = \begin{cases} \text{HALT}, &\text{if $n$ is 1} \\ f(n/2), & \text{if $n$ is even} \\ f(3n+1), & \text{if $n$ is odd} \end{cases} $$
It's known to halt for $n$ up to at least $5 × 2^{60} ≈ 5.764 × 10^{18}$, but in general it's an open problem.
-
10$\begingroup$ To stress my point from the comment beneath the question: the problem "does $f(n)$ halt for all $n$?" is computable. $\endgroup$– RaphaelCommented Jul 30, 2015 at 14:42
-
7
-
13$\begingroup$ @KyleStrand, Raphael is 100% correct. This is a common misconception. You have to trace through what the definition says very carefully, and then you may discover that your intuition doesn't quite match the definition. According to the definition of computability, it suffices that there exists a Turing machine to compute it -- it doesn't matter whether we know what that Turing machine is. On first seeing this many students think it's cheating, but it's not -- that's just a consequence of the definition. $\endgroup$– D.W. ♦Commented Nov 21, 2015 at 22:23
-
$\begingroup$ @D.W. Okay, that's the definition of a computable number. Raphael said that the problem is computable, which I would take to mean that an algorithm which is known to halt could determine whether or not the Collatz conjecture is valid. If this were the case, we could simply run such a program to discover whether or not the conjecture holds. (Also, I think a comment or two may have been deleted, since I put "trivial" in quotes...) $\endgroup$ Commented Nov 22, 2015 at 7:26
-
$\begingroup$ @Raphael Sorry to revive an old discussion without actually understanding the context much better than I did at the time, but in your original comment ("To stress my point from..."), are you disagreeing with this answer? That is, are you saying that because the "problem...is computable", it doesn't satisfy OP's requirement that "we can not tell whether [the program] terminate[s] or not"? $\endgroup$ Commented Dec 12, 2017 at 19:40
$\begingroup$
$\endgroup$
6
The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not.
"We" are not an algorithm =) There is no general algorithm that could determine if a given program halts for every program.
What are the simplest (smallest) known examples of such programs?
Consider the following program:
n = 3
while true:
if is_perfect(n):
halt()
n = n + 2
Function is_perfect checks whether n is a perfect number. It is unknown whether there are any odd perfect numbers, so we don't know whether this program halts or not.
-
11
-
4$\begingroup$ @PyRulez there is no proof that the computational power of human mind is equivalent to Turing Machine. The proof doesn't work, e.g. it is unknown how to simulate one mind in other one. $\endgroup$– avsmalCommented Aug 1, 2015 at 0:55
-
3$\begingroup$ @avsmal Okay, but it is extremely unlikely that we are capable of hypercomputation. $\endgroup$ Commented Aug 1, 2015 at 0:59
-
2$\begingroup$ @PyRulez John Lucas and Roger Penrose have suggested that the human mind might be the result of some kind of quantum-mechanically enhanced, "non-algorithmic" computation. That is some strong assumption. But at least our mind may have some source of uncertainty. And that is enough to break the proof: it is impossible to negate the "randomized" (for some suitable definition of what randomized mean) Turing Machine if it is unknown whether it halts. $\endgroup$– avsmalCommented Aug 1, 2015 at 1:11
-
8$\begingroup$ Is quantum computing considered hypercomputation? I assumed quantum computers could be perfectly simulated by turing machines - just a little slower. $\endgroup$ Commented Aug 4, 2015 at 3:25
$\begingroup$
$\endgroup$
5
You write:
The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not.
This is a non-sequitur, in both directions. You succumb to a common fallacy that is worth addressing.
Given any fixed program $P$, its halting problem ("Does $P$ always halt?") is always decidable, because the answer is either "yes" or "no". Even if you can not tell which it is, you know that one of the two trivial algorithms that answer always "yes" resp. "no" solves the $P$-halting problem.
Only if you require that the algorithm should solve the Halting problem for all¹ programs can you show that no such algorithm can exist.
Now, knowing that the Halting problem is undecidable does not imply that there are any programs nobody can not prove termination or looping of. Even if you are not more powerful than a Turing machine (which is only a hypothesis, not proven fact), all we know is that no single algorithm/person can provide such proof for all programs. There may be a different person being able to decide for each program.
Some more related reading:
- How can it be decidable whether $\pi$ has some sequence of digits?
- Human computing power: Can humans decide the halting problem on Turing Machines?
- Algorithm to solve Turing's "Halting problem"
- Program synthesis, decidability and the halting problem
- Is it possible to solve the halting problem if you have a constrained or a predictable input?
- Why are the total functions not enumerable?
So you see that your actual question (as repeated below) has nothing to do with whether the halting problem is computable. At all.
What are the simplest (smallest) known examples of [programs we don't know to halt or loop]?
This in itself is a valid question; others have given good answers. Basically, you can transform every statement $S$ with unknown truth value into an example, provided it does have a truth value:
$\qquad\displaystyle g(n) = \begin{cases}1, &S \text{ true},\\ g(n+1), &\text{else}.\end{cases}$
Granted, these are not very "natural".
- Not necessarily all, but "many" in some sense. Infinitely many, at least.
-
$\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$– RaphaelCommented Jun 9, 2016 at 10:02
-
$\begingroup$ To attempt to rephrase this for my own understanding, is it right to say that while there is no unique algorithm can determine whether any arbitrary given program halts, there may well be some program-specific algorithm to solve the halting problem of every possible program? $\endgroup$ Commented Dec 14, 2018 at 1:25
-
$\begingroup$ @AsadSaeeduddin It's "worse": for every given finite set of programs, the Halting problem is trivial. Every finite set is decidable. $\endgroup$– RaphaelCommented Dec 14, 2018 at 7:19
-
2$\begingroup$ great treatment of a subtle distinction. avsmal's incorrect answer above commits a fallacy of conflating lack of knowledge (i.e. there's no method known to mathematicians to determine whether odd perfect numbers exist) with undecidability of a specific $P$. Glad to see that Raphael has clarified that here. $\endgroup$ Commented Dec 3, 2021 at 20:38
-
$\begingroup$ I feel obligated to point out that there are fixed values of $P$ for which halting is ZFC-independent. This is a trivial corollary of Kleene's proof-enumeration variant of Gödel's (first) incompleteness theorem, and that argument in turn relies on the Halting Problem as its critical step. So it can be argued that the Halting Problem does indeed lead to the conclusion that some machines do not have a knowable halting-ness, if you accept "provable" as synonymous with "knowable" (itself debatable, since all machines that really do halt should provably halt under ZFC). $\endgroup$– KevinCommented Nov 24 at 4:16
$\begingroup$
$\endgroup$
Given that the Busy Beaver problem is not solved for a 5-state-2-symbol Turing machine, there must be a Turing machine with only five states and only two symbols which has not been shown to halt or not when started for an empty tape. That is a very short, concise, and closed program.
$\begingroup$
$\endgroup$
Any open problem regarding the existence of a number with particular properties gives rise to such a program (the one which searches for such a number). For example, take the Collatz conjecture; since we don't know if it is true, we also don't know if the following program terminates:
n:=1;
found:=false;
while not found do
s:={};
i:=n;
while i not in s do
add i to s;
if i even then i:=i/2 else i:=3i+1
if 1 not in s then found:=true;
n:=n+1
$\begingroup$
$\endgroup$
Write a simple program that checks whether for every n, $1 ≤ n ≤ 10^{50}$, the Collatz sequence starting with n will reach the number 1 in less than a billion iterations. When it has the answer, let the program stop if the answer is "Yes", and let it loop forever if the answer is "No".
We cannot tell whether this program terminates or not. (Who is we? Let's say "we" is anyone who could add a comment to my answer). However, someone with an incredibly powerful computer might tell. Some genius mathematician might be able to tell. There might be a rather small n, say n ≈ $10^{20}$ where a billion iterations are needed; that would be in reach of someone with a lot of determination, a lot of time, and a lot of money. But right now, we cannot tell.
$\begingroup$
$\endgroup$
5
the question is tricky because decidability (the CS equivalent formalization/ generalization of halting problem) is associated with languages so it needs to be recast in that format. this seems to not be pointed out much, but many open problems in math/ CS can be readily converted to problems (languages) of unknown decidability. this is because of a tight correspondence between theorem proving and (un)decidability analysis. for example (somewhat like the other answer wrt odd perfect numbers), take the twin primes conjecture which dates to the Greeks (over 2 millenia ago) and is subject to major recent research advances eg by Zhang/ Tao. convert it to an algorithmic problem as follows:
Input: n. Output: Y/N there exists at least n twin primes.
the algorithm searches for twin primes and halts if it finds n of them. it is not known if this language is decidable. resolution of the twin primes problem (which asks if there are a finite or infinite number) would also resolve the decidability of this language (if it is also proven/ discovered how many there are, if finite).
another example, take the Riemann hypothesis and consider this language:
Input: n. Output: Y/N there exist at least n nontrivial zeroes of the Riemann zeta function.
the algorithm searches for nontrivial zeroes (the code is not especially complex, its similar to root finding, and there are other equivalent formulations that are relatively simple, which basically calculate sums of "parity" of all primes less than x etc) and halts if it finds n of them and again, its not known if this language is decidable and resolution is "nearly" equivalent to solving the Riemann conjecture.
now, how about an even more spectacular example? (caveat, probably more controversial as well)
Input: c: Output: Y/N there exists an O(nc) algorithm for SAT.
similarly, resolution of decidability of this language is nearly equivalent to the P vs NP problem. however there is less obvious case for "simple" code for the problem in this case.
-
2$\begingroup$ Your "twin prime" language is decidable. If there is just a finite number $N$ of them, the answer is "Yes" for $n \le N$ and "No" otherwise, else always "Yes". Sure, we don't know $N$, but that is irrelevant, a (very simple) Turing machine answers. Just like the "Fermat's last theorem" language, "are there integers $a, b, c$ such that $a^n + b^n = c^n$ for $n$?", recently "we" found out this $N = 2$, Wiles' proof didn't change the language. $\endgroup$– vonbrandCommented Nov 21, 2015 at 22:21
-
4$\begingroup$ I'm not the downvoter, but all of the claims in this answer are wrong. All three of those problems are provably decidable (without needing to make any unproven assumptions). For why, study Raphael's answer closely. $\endgroup$– D.W. ♦Commented Nov 21, 2015 at 22:26
-
$\begingroup$ ok maybe the input needs to have the TM specified and the algorithm decides if the TM calculates the problem. have to think about it more... think there is some simple recipe for these types of problems basically connecting open problems to undecidable languages... but agreed this is rarely documented/ formulated in CS refs... have only found a few scattered refs... or maybe the input is a proof and the language verifies if the proof is correct... the other high voted answers mention odd perfect numbers, collatz problem etc... the programs are unknown to halt or not for specific constants. $\endgroup$– vznCommented Nov 22, 2015 at 1:30
-
$\begingroup$ sorry for the confusion! on some further thought the assertions are correct in the form that they describe simple programs not known to terminate (for all inputs) (ie the original question) and the failure of the overall idea sketched out/ pointed by DW is attempting to convert each into undecidable languages. will continue to ponder that latter construction idea looking for one that succeeds. another way of looking at it is that the problems can be seen as individual instances/ inputs for a halting problem solver but not really (known to be) equivalent to the halting problem itself. $\endgroup$– vznCommented Mar 15, 2016 at 1:43
-
$\begingroup$
$\endgroup$
Antihydra equivalent program (6-state turing machine)
Termination of the following program in arbitrary precision integer arithmetic is equivalent to the halting problem for a 6 state Turing machine with a specific (simple, explicit) initial tape condition:
int a = 8
int b = 0
while (true) {
if (a % 2 == 0) {
a = (a/2)*3
b += 2
} else {
if (b == 0)
break
a = ((a - 1)/2)*3 + 1
b -= 1
}
}
The Turing machine was discovered in June 2024 by the Busy Beaver challenge and is believed to be hard to decide. It was called "antihydra" and is described at: https://wiki.bbchallenge.org/wiki/Antihydra Given that they proved in Coq all 5-state turing machines, this is arguably the simplest open halting problem in existence today in the "states of an equivalent Turing machine" metric.
More context at: What are very short programs with unknown halting status?
answered Jul 10 at 10:08