30
13
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?
MaiaVictor
Posted 2015-07-30T12:35:51.993
Reputation: 3 939
45
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.
npostavs
Posted 2015-07-30T12:35:51.993
Reputation: 574
6 @KyleStrand See here.
@Raphael Eh? In that example, knowing the value of N is equivalent to having already solved the problem, thus making it a different problem. The resultant algorithm is essentially like printing a hard-coded answer. I don't see how that makes the original problem computable. – Kyle Strand – 2015-11-21T21:26:29.327
11@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. – D.W. – 2015-11-21T22:23:30.900
@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...) – Kyle Strand – 2015-11-22T07:26:05.283
3@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. – Raphael – 2015-11-22T08:36:35.257
1@Raphael Then does "the problem is computable" have any non-trivial meaning? – Kyle Strand – 2015-11-22T08:39:21.477
@KyleStrand Why yes, of course! For problems with infinitely many instances, things get interesting. – Raphael – 2015-11-22T08:40:25.847
@Raphael Okay, so for the given problem, "does $f(n)$ halt for all $n$", if you break it down into sub-problems, i.e. "does $f(n)$ halt for $n=$ ....", then is it no longer computable? That doesn't sound like a useful or interesting definition of the term "computable problem." But I think I need to read Martin Davis's halting problem paper, because it sounds like you're using a somewhat different definition of computability than I am (I've only read Turing's paper). – Kyle Strand – 2015-11-23T17:39:35.070
I do acknowledge that even using my (presumptive) definition of "computable problem" to mean "a problem that can be solved algorithmically in finite time", not having an algorithm is of course not equivalent to knowing that one cannot exist. – Kyle Strand – 2015-11-23T17:42:30.833
3@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. – Raphael – 2015-11-23T19:34:56.660
@Raphael I'm still not convinced I "went wrong" anywhere. "does $f(n)$ halt for all $n$" is a decision problem. This problem is computable IFF there exists an algorithm to decide whether each $n$ satisfies the Collatz conjecture. Such an algorithm may exist (in which case the problem is computable), but we don't know that that's the case. – Kyle Strand – 2015-11-23T19:49:07.017
3@KyleStrand you are making a valid point, but your use of terminology is out of agreement with the way these terms are used by everyone else. Your definition of "computable" is fine if you are inventing your own personal language for computer science concepts, but if you want to go into communication with others you may find your ideas gaining greater acceptance if you spend the time to appreciate the meanings that these terms ("computable" and "decidable") already have, as agreed upon by each person with whom you are arguing. – Wildcard – 2016-06-07T09:29:26.233
The problem "does f(n) halt for all n" is not decidable, because it is equivalent to the halting problem. Indeed, there's a more general result called Rice's Theorem that proves that any non-trivial property of a function is undecidable. Any of you claiming that "does f(n) halt for all n" is decidable, computable, recursively enumerable, or any other such term are in a state of error. – Tom Swirly – 2016-06-07T21:04:53.860
@TomSwirly You are wrong on both counts. The halting problem is only undecidable for (some) infinite sets of machines. Here we have a finite language, which is trivially decidable. I recommend you follow the first link from my answer. Secondly, you misunderstand Rice's theorem completely, and in a similar way. See here.
1@TomSwirly Side note: You should be careful with the strength of your statements. My guess is you've never taken a course on computability while many here have. As somebody who has graded exams on computability, let me assure you that you are wrong; finding out why will be a good learning experience for you and helpful for building your computational intuition. So you may want to take a step back and calmly check your references. – Raphael – 2016-06-08T08:18:29.477
@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"? – Kyle Strand – 2017-12-12T19:40:41.753
@KyleStrand No, the answer does indeed answer the question. My point is that the OP derived the question via a logical error, and they are probably not asking what they wanted to. The halting problem has nothing to do with the question asked, and answered here. Hence my answer
9To stress my point from the comment beneath the question: the problem "does $f(n)$ halt for all $n$?" is computable. – Raphael – 2015-07-30T14:42:39.350
@Raphael I'm not sure I follow. If the function does not halt for a particular n, then how could a "trivial" program determine for sure that that is the case? – Kyle Strand – 2015-08-04T03:29:24.627
33
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.
avsmal
Posted 2015-07-30T12:35:51.993
Reputation: 494
@PyRulez But we have intrinsic quantum randomness – noɥʇʎԀʎzɐɹƆ – 2016-06-07T21:43:40.370
8We are an algorithm. – PyRulez – 2015-07-31T17:25:13.770
@PyRulez In a way, but a very, very complex one. – ElementW – 2015-07-31T20:36:00.043
@gravgun The proof still works. Just read the proof, replacing "computer" with "human". – PyRulez – 2015-07-31T20:38:50.207
3@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. – avsmal – 2015-08-01T00:55:15.383
2@avsmal Okay, but it is extremely unlikely that we are capable of hypercomputation. – PyRulez – 2015-08-01T00:59:36.503
2@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. – avsmal – 2015-08-01T01:11:14.220
6Is quantum computing considered hypercomputation? I assumed quantum computers could be perfectly simulated by turing machines - just a little slower. – MaiaVictor – 2015-08-04T03:25:16.150
1@srvm that's true, quantum computers could be simulated by Turing machines with some slowdown. – avsmal – 2015-08-05T09:40:58.440
Hmm... that scar looks familiar. ;) Welcome. – Kaveh – 2015-08-05T21:15:59.493
11
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:
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".
Raphael
Posted 2015-07-30T12:35:51.993
Reputation: 69 237
Comments are not for extended discussion; this conversation has been moved to chat.
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? – Asad Saeeduddin – 2018-12-14T01:25:31.860
@AsadSaeeduddin It's "worse": for every given finite set of programs, the Halting problem is trivial. Every finite set is decidable. – Raphael – 2018-12-14T07:19:55.383
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. – Abhimanyu Pallavi Sudhir – 2020-07-26T04:42:15.807
7
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
Klaus Draeger
Posted 2015-07-30T12:35:51.993
Reputation: 2 063
7
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.
not-a-user
Posted 2015-07-30T12:35:51.993
Reputation: 171
0
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.
vzn
Posted 2015-07-30T12:35:51.993
Reputation: 10 652
2Your "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. – vonbrand – 2015-11-21T22:21:26.950
3I'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. – D.W. – 2015-11-21T22:26:04.210
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. – vzn – 2015-11-22T01:30:08.020
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. – vzn – 2016-03-15T01:43:13.287
for more bkg on this approach see refs [d10,d11], Evaluating the Complexity of Mathematical Problems by Calude(s) & many other related refs on that pg
1Would the downvoter explain what is wrong with this answer? – MaiaVictor – 2015-08-04T22:28:54.513
0
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.
gnasher729
Posted 2015-07-30T12:35:51.993
Reputation: 21 531
The Halting Problem: "In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an arbitrary input, whether the program will finish running or continue to run forever." I think your question is "Give examples of specific finite computer programs such that there exists no specific single Turing Machine which when given that specific finite computer program and arbitrary input for that program, can answer correctly whether that program halts on that input. " But the answers you selected only satisfies: [cont] – Craig Hicks – 2017-12-11T19:31:54.323
[cont] But the answers you selected only satisfies: "We don't know if such a specific Turing Machine exists or not". (@KyleStrand this may be related to your comments?) – Craig Hicks – 2017-12-11T19:33:54.097
And to make things worse, "we don't know" is rather imprecise. Who is we? How do we know there are not other lifeforms which do know? How do we know there are not other lifeforms which do know, and which are reading this post right now and laughing? – Craig Hicks – 2017-12-11T19:43:06.380
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. – htm11h – 2015-07-30T14:57:44.463
3
similar question What is the smallest Turing machine where it is unknown if it halts or not? / [cstheory.se]
– vzn – 2015-07-30T15:47:45.197I 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. – Rob – 2015-07-30T18:31:20.073
1@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. – Kyle Strand – 2015-08-04T03:21:49.480
@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. – Rob – 2015-08-04T15:01:57.493
@Rob But knowing that an algorithm can't exist is useful, because it saves you the wasted time of trying to think of one. Similarly, an algorithm with an extremely long running time can inspire the discovery of a more efficient algorithm, or could become practical given sufficient computational resources. – Kyle Strand – 2015-08-04T15:52:25.727
It's just another instance of being in a situation where you can't quite prove that your code is correct (ie: produce the right answer, runs in time constraints, runs in space constraints, runs in power constraints, etc.). If you are parsing input, try to require regular/context-free recognition. You can still pass in constraints so that the code can halt itself when it exceeds any resource limit.
The only interesting result is when you can prove that the code gives a positive answer within explicit resource constraints, but this isn't more special than other correctness properties. – Rob – 2015-08-04T18:54:29.710