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$
11
-
$\begingroup$ You are contradicting in your responses.....Thanks! But the halting program assumes knowledge of the source. ...If this is true you have answered your question. The halting program would already know. Imagine a system controlling a sign, it is always illuminated and flashing, when does it shut off? Power failure, power switch, or during the flash sequence. Or given a battery back-up and generator, never. $\endgroup$– htm11hJul 30, 2015 at 14:57
-
3$\begingroup$ similar question What is the smallest Turing machine where it is unknown if it halts or not? / Theoretical Computer Science $\endgroup$– vznJul 30, 2015 at 15:47
-
$\begingroup$ I would add that the halting problem is only a problem if you don't put a timing upper bound. Surely there is no difference in practice between getting an answer too late to be of any use and never getting an answer. You can ask whether a program will return an answer within a number of steps, like a real-time definition of correctness. If you can't guarantee a timely answer, then you simply have a program that lacks a correctness guarantee. $\endgroup$– RobJul 30, 2015 at 18:31
-
1$\begingroup$ @Rob That's not actually true. If you don't know whether a machine will halt, you can wait indefinitely to see whether it halts; after a millennium, you still won't know whether or not it will stop, say, the next day. $\endgroup$– Kyle StrandAug 4, 2015 at 3:21
-
$\begingroup$ @KyleStrand I'm agreeing with you. But I'm also saying that it's a totally overblown issue in practice, because all realistic computations are subject to deadlines (milliseconds to months). If you need an answer in 5 seconds for it to be useful, the only thing that matters is whether you can guarantee an answer in 5 seconds. Suppose that you could guarantee an answer given an indeterminate amount of time to compute. That would be a useless guarantee. $\endgroup$– RobAug 4, 2015 at 15:01
|
Show 6 more comments
7 Answers
$\begingroup$
$\endgroup$
19
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.
-
9$\begingroup$ To stress my point from the comment beneath the question: the problem "does $f(n)$ halt for all $n$?" is computable. $\endgroup$– Raphael ♦Jul 30, 2015 at 14:42
-
7
-
12$\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. ♦Nov 21, 2015 at 22:23
-
3$\begingroup$ @KyleStrand You have to get rid of the idea that the program has to solve the problem. It does not. It just has to output the answer, which is a trivial task. Algorithmically, problems with finite sets of instances are all boring since we can hardcode the answers. (And even if we don't know the answers, we still know that there is a correct algorithm.) In general, when showing that there is no algorithm for something, you don't get to make any assumptions on how it's going to work. Our lack of imagination does not provide a proof. $\endgroup$– Raphael ♦Nov 22, 2015 at 8:36
-
3$\begingroup$ @KyleStrand Afaik, I use the standard definition of computability as it is taught today (and, afaik, has been for decades). I recommend you absorb the answers and linked material and work out where you went wrong. It does not make sense for me and others to repeat the same things over and over. One more try: the definition of computability is inherently existential, not constructive. As long as you think within the realms of classical logic, there is no need at all to be able to hand over a "solving" algorithm -- we just have to show that there is one that gives the right answers. $\endgroup$– Raphael ♦Nov 23, 2015 at 19:34
$\begingroup$
$\endgroup$
10
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.
-
9
-
3$\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$– avsmalAug 1, 2015 at 0:55
-
3$\begingroup$ @avsmal Okay, but it is extremely unlikely that we are capable of hypercomputation. $\endgroup$– PyRulezAug 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$– avsmalAug 1, 2015 at 1:11
-
7$\begingroup$ Is quantum computing considered hypercomputation? I assumed quantum computers could be perfectly simulated by turing machines - just a little slower. $\endgroup$ 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$– Raphael ♦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$ 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$– Raphael ♦Dec 14, 2018 at 7:19
-
$\begingroup$ A computer can absolutely simulate a human brain. It can also simulate the brains of every human on Earth, and the physical process that gives rise to every human brain to ever exist in future. I don't think your dismissal of the question is correct. $\endgroup$ Jul 26, 2020 at 4:42
-
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$ Dec 3, 2021 at 20:38
$\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$
6
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.
-
1$\begingroup$ Would the downvoter explain what is wrong with this answer? $\endgroup$ Aug 4, 2015 at 22:28
-
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$– vonbrandNov 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. ♦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$– vznNov 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$– vznMar 15, 2016 at 1:43
$\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.
