Whenever people ask about the halting problem as it pertains to programming, people respond with "If you just add one loop, you've got the halting program and therefore you can't automate task"

Makes sense. If your program has an infinite loop, then when your program is running, you have no way of knowing whether the program is still crunching input, or if it is just looping infinitely.

But some of this seems counter intuitive. What if I was writing a halting problem solver, which takes source code as its input. rascher@localhost$ ./haltingSolver source.c

If my code (source.c) looks like this:

for (;;) {  /* infinite loop */  }

It seems like it'd be pretty easy for my program to see this. "Look the loop, and look at the condition. If the condition is just based on literals, and no variables, then you always know the outcome of the loop. If there are variables (eg while (x < 10)), see if those variables are ever modified. If not, then you always know the outcome of the loop."

Granted, these checks would not be trivial (calculating pointer arithmetics, etc) but it does not seem impossible. eg:

int x = 0
while (x < 10) {}

could be detected. along with - albeit not trivially:

int x = 0
while (x < 10)
   if (x == 10)
      x = 0

Now what about user input? That is the kicker, that is what makes a program unpredictable.

int x = 0;
while (x < 10) 
   scanf("%d", &x); /* ignoring infinite scanf loop oddities */

Now my program can say: "If the user enters a 10 or greater, the program will halt. On all other input, it will loop again."

Which means that, even with hundreds of inputs, one ought to be able to list the conditions on which the program will stop. Indeed, when I write a program, I always make sure someone has the ability to terminate it! I am not saying that the resulting list of conditions is trivial to create, but it doesn't seem impossible to me. You could take input from the user, use them to calculate pointer indexes, etc - but that just adds to the number of conditions to ensure the program will terminate, doesn't make it impossible to enumerate them.

So what exactly is the halting problem? What am I not understanding about the idea that we cannot write a problem to detect infinite loops? Or, why are "loops" such an oft-cited example?


So, let me change the question a little bit: what is the halting problem as it applies to computers? And then I will respond to some of the comments:

Many people have said that the program must be able to deal with "any arbitrary input." But in computers, there isn't ever any arbitrary input. If I only input a single byte of data, than I only have 2^8 possible inputs. So, as an example:

int c = getchar()

switch (c) {
   case 'q':
      /* quit the program */

All of the sudden, I have just accounted for all of the possibilities. If c has the bit pattern 0x71, it does one thing. For all other patterns, it does something else. Even a program that accepts arbitrary string input is never really "arbitrary", since resources are finite, which means that while the theory of "arbitrary" applies... it isn't exactly one-to-one with the practice.

The other example people cited is this:

while (n != 1)
    if (n & 1 == 1) 
        n = 3 * n + 1;
        n /= 2;

If n is a 32-bit integer... then I can visually tell you whether or not this will halt.

I guess this edit isn't asking anything, but the most convincing example I've seen is this one:

Assume that you have your magical program/method to determine that a program halts.

public bool DeterminesHalt(string filename, string[] args){
    //runs whatever program you tell it do, passing any args
    //returns true if the program halts, false if it doesn't

Now lets say we write a small piece of code such as...

public static void Main(string[] args){
    string filename = Console.ReadLine(); //read in file to run from user
    if(DeterminesHalt(filename, args))

So for this example, we can write a program to do the exact opposite of our magical halting method does. If we somehow determine that a given program will halt, we just hop into an infinite loop; otherwise if we determine that the program is in an infinite loop, we end the program.

Then again, if you intentionally write a program which contains an infinite loop... "solving the halting problem" is kind of moot, isn't it?

  • 20
    Write a program that only terminates when it finds a solution to an open question; like say, the first perfect odd number. Now apply your technique for solving the halting problem to that program. The halting problem isn't about loops, its about computation theory. – Kevin Montrose Jul 10 '09 at 18:32
  • @Kevin, or even better, take as input the program that calculates the last perfect number. It might halt, it might not. It hasn't been proved that the series is infinite or finite. – Bob Cross Jul 11 '09 at 0:35
  • 3
    You shouldn't use C programs to show problems of computational theory. It is important that you choose a very simple model to make things easier to comprehend. You can compose so many odd cases with real programming languages that it becomes nearly impossible to understand. This doesn't happen with Turingmachines or WHILE-Programms or µ-recursive Functions. And in the end they are equally powerful to any normal programming language. – pmr Jul 12 '09 at 17:24
  • 3
    The point of your final example (with the DeterminesHalt method), is that your method is WRONG in that instance. As in, if you run Main on Main.java, it will be tantamount to saying "This program halts if it runs forever, and runs forever if it halts". A paradox! Be wary: your computer may melt. – agorenst Aug 26 '09 at 15:09
  • Many questions and not a single one which actually answers the original question. – doubleOrt Jun 11 '18 at 9:08

22 Answers 22


EDIT (much later than original answer): MarkCC of Good Math, Bad Math recently wrote up an excellent discussion of the Halting problem with concrete examples.

The halting problem is basically a formal way of asking if you can tell whether or not an arbitrary program will eventually halt.

In other words, can you write a program called a halting oracle, HaltingOracle(program, input), which returns true if program(input) would eventually halt, and which returns false if it wouldn’t?

The answer is: no, you can’t.

Following up on questions about whether the input to the Halting problem is relevant or a red herring: Yes, the input is important. Also, there seems to be some confusion in that I see "infinite" being used where "arbitrary" is more correct.

Practical example: Imagine that you are working in a QA position and you are to write a halting checker program (aka an oracle) that will confirm that for any arbitrary program written by the development team (D) and any arbitrary input provided by the end-user (I), program D will eventually halt when given input I.

Cue manager voice: "Ho ho, those goofy users, let's make sure that no matter what garbage they type, our server tasks will never end up in an endless loop. Make it so, code monkey!"

This seems like a great idea, right? You don't want your server to hang, right?

What the halting problem is telling you is that you are being handed an unsolvable task. Instead, in this particular case, you need to plan for tasks that run past a threshold time and be ready to cancel them.

Mark uses code instead of input to illustrate the problem:

def Deciever(i):
  oracle = i[0]
  in = i[1]
  if oracle(Deceiver, i):
    while True:
    return i

In my discussion in the comments, I went the route of malicious input manipulation to force an unsolvable problem. Mark's example is far more elegant, using the halting oracle to defeat itself:

So, the input to Deceiver is actually a list of two elements: the first one is a proposed halting oracle. The second is another input. What the halting killer does is ask the Oracle: “Do you think I’ll halt for input i?”. If the oracle says, “Yes, you’ll halt”, then the program goes into an infinite loop. If the oracle says “No, you won’t halt”, then it halts. So no matter what the oracle says, it’s wrong.

Said another way, without cheating, reformatting inputs, countable / uncountable infinities or anything other distractions, Mark has written a piece of code that can defeat any halting oracle program. You cannot write an oracle that answers the question of whether Deceiver ever halts.

Original answer:

From the great Wikipedia:

In computability theory, the halting problem is a decision problem which can be stated as follows: given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input.

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines. Copeland (2004) attributes the actual term halting problem to Martin Davis.

One of the critical points is that you have no control over either the program or the input. You are handed those and it's up to you to answer the question.

Note also that Turing machines are the basis for effective models of computability. Said another way, everything that you do in modern computer languages can be mapped back to these archetypical Turing machines. As a result, the halting problem is undecidable in any useful modern language.

  • 3
    The fact that you have no control over the input to the program is not really crucial, because given any (program,input) pair (P,I), you can trivially create a new program Q which takes no input and does exactly what P does on I. (And ask whether Q halts.) – ShreevatsaR Jul 13 '09 at 2:46
  • 2
    No, the set of all PxI is still countably infinite. (The Cartesian product of any two countable sets is countable!) I'm not saying the problem is trivialized, on the contrary I was explaining that the "input" part is not what makes the problem hard; even simply deciding whether programs that take no input halt is undecidable. – ShreevatsaR Jul 13 '09 at 3:53
  • 1
    The input to a Turing machine is a sequence of symbols on its input tape, and thus countable. (For a program, whether its input is a sequence of digits or something else, the set of all "definable numbers" is still countable.) So as far as the halting problem is concerned, input is countable. (There is a model of "real computation" introduced by Blum-Shub-Smale, but I'm not familiar with it and it doesn't seem to be much used.) I don't think this point is worth emphasizing, just trying to avoid the idea that "If I write only programs that don't take input, I can decide whether they halt" :-) – ShreevatsaR Jul 14 '09 at 15:52
  • 1
    @ShreevatsaR, I agree that any particular input is countable in extent. The general set of possible inputs is not. I agree with you, though, that it's not enough to say "hey, what if I hard-code the input? Then I'll be on Easy Street!" ;-) – Bob Cross Jul 14 '09 at 22:36
  • 1
    @Donal, no, you can't. You're assuming a priori knowledge. You don't know what input I'm going to provide ahead of time and I have complete freedom of input. After I provide input, you could rewrite the program as if that input was a pre-provided constant but that would be a waste of time. You aren't solving the general problem at that point, you're trying to solve one specific example. This is equivalent to saying "if I already know the answer, I can prove it correct." – Bob Cross Oct 8 '10 at 12:50

To solve the halting problem, you'd have to develop an algorithm that could determine whether any arbitrary program halts for any arbitrary input, not just the relatively simple cases in your examples.

  • 2
    +1 for non-trivial test cases! – Ed S. Jul 10 '09 at 18:38
  • There is a functional language called Idris that has a notion of complete functions which are proven to complete in a finite amount of time given any input that conforms to the type definition for the function. The compiler will report if your function is complete. – dansalmo Nov 28 '18 at 23:12

Here is a simple explanation of the proof that the halting problem is undecidable.

Assume you have a program, H, which computes whether or not a program halts. H takes two parameters, the first is a description of a program, P, and the second is an input, I. H returns true if P halts on input I, and false otherwise.

Now write a program, p2, which takes as it's input the description of another program, p3. p2 calls H(p3, p3), then loops if H returns true and halts otherwise.

What happens when we run p2(p2)?

It must loop and halt at the same time, causing the universe to explode.

  • 34
    I hate when that happens. – Tom Hubbard Jul 10 '09 at 19:04
  • 3
    can someone explain. H(p3,p3) and p2(p2). – OnePunchMan Aug 29 '16 at 14:24
  • 1
    when h takes p2, p2, it will deduce that p2's intent is recursive since it obviously keeps delegating work to repeating patterns, and say that it won't terminate, there's no need to run the program, you just use the language calculus and make inferences about how sequences of environment transformations interact. the only undecidable programs seem to be those with undecidable algebras, such as integers, doubles, if such conditionals are O(n) or above, they are undecidable since we can't show they terminate without running them. – Dmitry Mar 12 '17 at 14:53
  • Yes, Its a nice ans but please add explaination by taking few cases. – roottraveller Jul 14 '17 at 6:57
  • How do you prove that such p3 program exists? If no such p3 program exists, p2 never halts. – fferri Aug 21 '17 at 9:01

This has been beaten to death so well that there is actually a poetic proof, written in the style of Lewis Carroll Dr. Seuss by Geoffrey Pullum (he of Language Log fame).

Funny stuff. Here's a taste:

Here’s the trick that I’ll use – and it’s simple to do.
I’ll define a procedure, which I will call Q,
that will use P’s predictions of halting success
to stir up a terrible logical mess.


No matter how P might perform, Q will scoop it:
Q uses P’s output to make P look stupid.
Whatever P says, it cannot predict Q:


There's an OK proof the Halting Problem on wikipedia.

To illustrate, exactly, why just applying some technique to loops is insufficient, consider the following program (pseudocode):

int main()
  //Unbounded length integer
  Number i = 3;

    //example: GetUniquePositiveDivisiors(6) = [1, 2, 3], ...(5) = 1, ...(10) = 1, 2, 5, etc.
    Number[] divisiors = GetUniquePositiveDivisiors(i);
    Number sum = 0;
    foreach(Number divisor in divisiors) sum += divisor;

    if(sum == i) break;


Can you think of an approach that will return true if this code halts, and false otherwise?

Think Carefully.

If by chance you're in serious contention for a Fields medal, imagine some code for these problems in place of the above.

  • This, of course, on it's own is not a proof. Sure, it's unlikely that there's a halting problem solver that also knows the answers to all open problems in mathematics. (It's also impossible, thanks to incompleteness.) But just appealing to its extreme difficulty doesn't constitute a proof of its impossibility. I certainly grant that this is a good way to gain intuition about the problem, and that combined with incompleteness there is a proof to be found down this road. The diagonalization proof given on Wikipedia, OTOH, is correct. – Doug McClean Jul 13 '09 at 0:42
  • I could copy the proof from wikipedia into my answer, or I could cite it and then use an example to illustrate why intuitive "solutions" to the halting problem are incorrect; using about the same space either way. I went with the later, as I believe its more useful than a formal proof in the context of this question. – Kevin Montrose Jul 13 '09 at 1:03
  • I don't disagree with that. I'm just throwing it out there so nobody gets confused. I thought it was a good answer. – Doug McClean Jul 13 '09 at 4:09


Sounds like someone over generalizing the application of the halting problem. There are plenty of particular loops that you can prove terminate. There exists research that can perform termination checking for wide classes of programs. For instance in Coq you are limited to programs that you can prove terminate. Microsoft has a research project called Terminator that uses various approximations to prove that programs will terminate.

But, remember, the halting problem isn't just about toy examples. Neither of those solves the general 'halting problem', because they don't work for every program.

The problem is that the halting problem says that there exist programs that you have no way to know if they will terminate without running them, which means that you may never get done deciding if they halt.

An example of a program that may or may not halt (in Haskell):

collatz 1 = ()
collatz !n | odd n     = collatz (3 * n + 1)
           | otherwise = collatz (n `div` 2)

or in something more accessible:

while (n != 1)
    if (n & 1 == 1) 
        n = 3 * n + 1;
        n /= 2;

Given every integer >= 1, will this program halt? Well, it has worked so far, but there is no theorem that says it will halt for every integer. We have a conjecture due to Lothar Collatz that dates back to 1937 that it holds, but no proof.

  • +1 for at least mentioning the very rich area of program verification. Sure, the halting problem is undecidable in general, but there is a large class of programs that can be proved to halt. – ShreevatsaR Jul 10 '09 at 19:05
  • See the notion of complete functions in a functional language called Idris as an example of this being built in to a compiler. – dansalmo Nov 28 '18 at 23:17

Turing's great example was self-referential - Suppose there IS a program that can examine another one and determine whether or not it will halt. Feed the halting-program-checker ITSELF into the halting-program-checker - what should it do?

  • @Bob: Thanks for the edit! Fat fingers. – n8wrl Jul 10 '09 at 18:23
  • @n8wrl, no problem. I did the exact same thing in my answer.... – Bob Cross Jul 10 '09 at 18:29
  • 18
    This proves nothing: the halting-program-checker can simply say "Yes, it halts" and there's no contradiction. The argument is self-referential, but it's subtler than what you say. – ShreevatsaR Jul 10 '09 at 19:01

In reference to the sub-point "people respond with "If you just add one loop, you've got the halting program and therefore you can't automate task"", I'll add this detail:

The posts that say that you cannot algorithmically compute whether an arbitrary program will halt are absolutely correct for a Turing Machine.

The thing is, not all programs require Turing Machines. These are programs that can be computed with a conceptually "weaker" machine --- for example, regular expressions can be embodied entirely by a Finite State Machine, which always halts on input. Isn't that nice?

I wager that when the people say "add one loop", they're trying to express the idea that, when a program is complex enough, it requires a Turing Machine, and thus the Halting Problem (as an idea) applies.

This may be slightly tangential to the question, but I believe, given that detail in the question, this was worth pointing out. :)

  • 2
    It depends on whether the program can be shown to be Primitive Recursive or not. With a PR functional program (or its equivalent in some other style of programming) every loop can be shown to terminate because you can find a metric of how much work it has left to do which monotonically decreases. But beyond PR are General Recursive functions where such metrics are not known to exist, and the Halting Problem shows why there's no algorithm for finding such metrics. – Donal Fellows Oct 8 '10 at 10:56

Here is a program that the halting problem will never be able to solve.




public static void Main(string[] args){
    if(DeterminesHalt(filename, args))


No matter how many input checks you do, there is no possible solution to determine whether EVERY program written halts or not.

  • 7
    You forgot the contradiction. Run your Main on itself: if it determines it will halt, then it will run forever. But if it determines it will run forever, then it will halt. Therefore, the determination cannot be made, and the DeterminesHalt cannot exist. – Cypher2100 Jul 11 '09 at 22:15
  • I agree with @Cypher2100. Check Graphics Noob's answer above, which demonstrates the full proof. – Vicky Chijwani Nov 18 '12 at 17:12

A lot of interesting specific examples/analogies so far. If you want to read deeper into the background, there's a good book on Turing's original paper, The Annotated Turing, by Charles Petzold.

In a related, sideways-sorta, vein, there's a really neat essay up on the web, Who Can Name the Bigger Number? which brushes on Turing machines and Ackermann functions.


There are lots of good answers already, but I haven't seen anyone address the fact that, in a sort of selective blending of theory and practicality, the Halting Problem really is solvable.

So first of all, the Halting Problem is basically the task of writing a program which takes any arbitrary second program and determines whether the secondary program will halt on an arbitrary input. So you say "Yes this program will halt on this input" or "No it won't". And in fact, it is unsolvable in the general case (other people seem to have provided proofs of this already) on a Turing Machine. The real problem is that you can kind of find out whether something is going to halt by running it (just wait until it halts), but you can't really find out whether something is going to NOT halt by running it (you'll just keep waiting forever).

This is a problem on a Turing Machine which, by definition, has an infinite amount of memory and thus infinitely many states. However, our computers have only a finite amount of memory. There are only so many bits on the computer. So if you could somehow keep track of all of the previous states (bit configurations) you've seen while running the program, you can guarantee that your checker will never go into an infinite loop. If the secondary program eventually halts, you say "Yes, this program will halt on this input". If you see the same bit configuration twice before it halts, you know "No it won't". Probably not of great technical importance, but it's good to know that a lot of times the really "hard" problems we face are harder in theory than in practice.

  • 2
    Oh dear. You need to have a think about how many possible states a computer with 4 GB of RAM can get into! – Daniel Earwicker Jul 10 '09 at 19:13
  • 2
    You can consider computers DFAs, and then yes the halting problem is solvable. However, I wouldn't call this practical by any means. If you consider the hard-drive as part of the state machine, you've got more states than you could ever hope to enumerate. – Kevin Montrose Jul 10 '09 at 19:22
  • Sure... it's still not practically solvable. But it's theoretically solvable. And who doesn't enjoy a little useless theory? – Ambuoroko Jul 10 '09 at 19:26
  • No, it's not really theoretically solvable, that's the whole point! And why bring hard drives into it? Figure out how many states a C-64 could be in. By the way, there are only 10^80 atoms in the entire universe. – Daniel Earwicker Jul 10 '09 at 19:41
  • 1
    My point was mostly meant as a sort of "fun fact", but I also intended to illustrate some differences between the theory and reality. When you PROVE the Halting Problem is unsolvable, you are actually proving it for a Turing Machine. The Halting Problem is provably solvable on an actual computer. If you had a Turing Machine run the secondary program within a simulated computer, the Turing Machine would be guaranteed to eventually halt, and thus will have solved the Halting Problem (on the simulated computer) – Ambuoroko Jul 10 '09 at 19:48

It's a variant of the halting dog problem, except with programs instead of dogs and halting instead of barking.


A proof from another perspective

Suppose we got a cpu with instructions like mov, add, jmp, but without in nor out. And we got memory. Not like other cpus, this one has another register, called paraReg. This register is like a file, we can mov unlimited content into it, get the size of it, seek to the middle of it, delete some of the content from it, which are done through some additional instructions .

Before we start, let's define some words. A program is a bunch of instructions, which is a string. Before we run a program, we clear all the registers and memory to zero except paraReg , which holds the parameter(a string), and then put the program into memory location zero and set ip register to zero. A process is when a program is running.

Now the halting problem can be stated like this : given any program, called proObj(if it takes a parameter para0, we add an instruction on the first line of it: mov paraReg , para0), is there a program which takes proObj as the parameter and can decide whether proObj will halt when proObj starts to run on paraReg set to zero?

Suppose we got such a program, called p1. Then we can create another program, called p2 which takes a parameter para0. Through p1, we can tell if a program whose content is para0, whose parameter is para0, will halt or not.(We do it this way. Construct a program whose first line is [mov paraReg , para0], the rest is para0. Name this program pro0. Then we set paraReg to pro0 and call p1. ) If it will halt,we let p2 enter into an infinite loop, otherwise we let p2 halt.

If we put p2 into paraReg and run p2, will the process halt or not? If it halts, from the definition of p2, we know when we put p2 into paraReg and run p2, it should not halt; likewise , if it doesn't halt, we know when put p2 into paraReg and run p2 ,it should halt. Then we can say there is no p2, and there is no p1.


You listed a few of the simple cases.

Now, think about thinking of all of the rest of the cases.

There are an infinite number of possible scenrios, you would have to list them all.

Unless of course you could generalize it.

That is where the halting problem comes in. How do you generalize it?


How does your program resolve the Collatz conjecture ?


From Programming Pearls, by Jon Bentley

4.6 Problems

5. Prove that this program terminates when its input x is a positive integer.

while x != 1 do
    if even(x)
        x = x/2
        x = 3*x +1
  • for more explanation about this problem see for example: cecm.sfu.ca/organics/papers/lagarias The point is: this is not yet been proven. BTW: thx for making me lookup the problem, hehe, i just had to know. – Emile Vrijdags Jul 10 '09 at 20:11
  • it looks like a small, easy problem. But, surprise! It's an open problem of mathematics :-D I posted basically for fun and as a challenge ;) – Nick Dandoulakis Jul 11 '09 at 5:09

I would suggest to read this: http://en.wikipedia.org/wiki/Halting_problem, especially http://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof in order to understand why this problem can't be solved in algorithmic way.


Assume that you write an algorithm that can check any arbitrary piece of code and tell if it halts.

Now give your algoritm itself to check.


The precise definition of the problem is that you need to write a program that does the following: - takes an arbitrary program - determines if the program halts given any arbitrary finite input into the program

However, this is a really high bar. There are many partial solutions to the halting problem, but no general solution. Even worse, even finding programs that partially solve the halting problem is known to be difficult:

BBC h2g2 article on the halting problem

If you have truly solved the halting problem, there work on sites like rentacoder.com for you. A few months ago there was a post on one of them from a user named ATuring who offered a contract to solve the halting problem. :)


You may find it helpful to consider the story of the guy who mows the lawn of anyone who doesn't mow their own lawn, and ask yourself whether or not he mows his own lawn.


Yet another example. I recently ran into something called hailstone numbers. These numbers form a sequence with these rules

f(n) is odd  -  f(n+1) = 3*f(n)+1
f(n) is even -  f(n+1) = f(n)/2

Currently, it is assumed that all starting points will eventually arrive at 1, and then repeat 4,2,1,4,2,1,4,2,1... However there is no proof for this. So right now the only way to determine if a number terminates when fed into the hailstone sequence is to actually compute it until you arrive at 1.

This is the key to how I understand the halting problem. How I understand it is that you cannot for sure know a that a program will/will not halt unless you actually run the program. So any program that you write that could give you an answer for sure to the halting problem, would have to actually run the program.


The significance of the halting problem does not lie in the importance of the problem itself; on the contrary, automated testing would be of little practical use in software engineering (proving that a program halts does not prove that it is correct, and in any case the hypothetical algorithm only provides proof for a given finite input, whereas a real-life software developer would be more interested in a test for all possible finite inputs).

Rather, the halting problem was one of the first to be proven undecidable, meaning that no algorithm exists which works in the general case. In other words, Turing proved more than 70 years ago that there are some problems which computers cannot solve -- not just because the right algorithm has not yet been found, but because such an algorithm cannot logically exist.

Your Answer

