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)
{
x++;
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?

**UPDATE**

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;
else
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))
for(;;);
else
return;
}
```

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?

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.

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?

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?

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.

How does your program resolve the Collatz conjecture ?

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:
continue
else:
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.

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

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

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))
for(;;);
else
return;
}
```

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.

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

"If you just add one loop, you've got the halting program and therefore you can't automate task"

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;
else
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.

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.

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;
while(true)
{
//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;
i+=2;
}
}
```

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

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

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
else
x = 3*x +1
```

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.

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.

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.

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:

P is right when it’s wrong, and is false when it’s true!

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.

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

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

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.

Similar Questions

I am just starting to learn MPI. The implementation is MPICH2. The first thing I encountered is SMPD i.e Simple Multi-Purpose Daemon. I want to know what exactly it is and how it is related to MPI M

I am trying to figure out what exactly is Appdomain recycling? When a aspx page is requested for the first time from a DotNet application, i understand that an appdomain for that app is created, and r

GCC has C extension which allows using nested functions. Actually, I don't understand what exactly can higher order functions in Haskell do (or other pure functional language) that C (function pointer

Can anyone explain what the target oldconfig does exactly in the Linux kernel makefile? I see it referenced in some build documentation but never explained what it does exactly. Thank you, Fred

What happens (exactly) if you leave out the copy-constructor in a C++ class? Is the class just memcpy'd or copied member wise?

According to berks help update, the command is supposed to: Update the cookbooks (and dependencies) specified in the Berksfile (Yes ... that's all it says!). But what exactly does this mean? And

While going through JPA, QueryDSL they all have included the concept of type-safe queries. But what exactly is it? According to blogs/articles, I guess it is a feature of JPA/QueryDSL that validates t

I've often heard about handles, what exactly are those? Edit: For instance I have heard about: windows handles event handles file handles and so on. Are those things the same? Or they are some abstr

What does if(a) exactly check in javascript? Can it check undefined? Can it check null? Can it check an empty string? When do we need to use typeof a == 'undefined' or it could be covered by if(a)?

I understand what a datatype is (intuitively). But I need the formal definition. I don't understand if it is a set or it's the names 'int' 'float' etc. The formal definition found on wikipedia is conf

I came across this wordpress build-in function get_page_by_path, but I am still confused after reading the documentation, can anyone explain better to me what does it exactly do and what value it re

what does this exactly mean? public class Deck<T extends Card> What does the T extends Card mean? Does this imply something about the class Card? thanks!

As sou can see from the screenshot most of the time spent is waiting for a server response (thats the purple coloured area). What exactly is that server response time? Is the server too slow? Is my co

I've read lots of articles about intent filters and I really can't understand exactly what they do? so please if anybody can explain to me with a clear example what is the role of intent filters exact

What exactly is int in C#? Is it a keyword, or is it a class derived from system.ValueTypes? If it is a keyword then how does the following lines compile int i = new int(); // If int is not a class th

Can you please help me for this question, I need to know the What is the Quality check exactly when compared to Quality Assurance? Thanks in advance.

I don't understand what is exactly a builder in CDT, and what is the relationship with the C/C++ Build content. I set up SCons in the C/C++ Build confuguration. It does work : I made two configura

random.shuffle(lst_shuffle, random.random) I know the latter part is an optional argument. But what does it do exactly. I don't understand what this mean. This is from the docs. random.random()¶ Re

I have spent sometime trying to understand what a baseUrl is(from learning Zend Framework), but it's surprising that for such a ubiquitous utility, not a single expert or blogger has even attempted

What does a rack handler do exactly, i.e. can someone explain in pseudo-code the steps that a rack handler takes to deliver a result for a request?

As on the picture: Could someone help me understand what exactly what delta means in the gradient descent algorithm?

I read elsewhere on here that it's possible to re-skin the Apple Game Center? Few questions about that.. 1) What exactly can you re-skin? all of it? or just some parts? 2) Is it wise to re-skin the GU

anybody know what exactly below code does? SPWeb.Features.Add(Guid, bool) Does it use the .xmls in Template\Features\<-myFeature-> to install the feature and activate it? Or just activate it? Or

From my understanding, AJAX requires the use of the XMLHttpRequest object. What I am confused on is the source of where the XMLHttpRequest object is connected to? In the school projects, I have connec

If you look at LienarLayout's source code, you'll notice that there is an annotations called @ViewDebug.ExportedProperty. My questions is: what is @ViewDebug.ExportedProperty exactly?

What exactly does the word patch mean when refering to 'submitting a patch'? I've seen this used a lot, especially in the open source world. What what does it mean and what exactly is involved in subm

I am using Scrum with a small team for the first time and I have gone through many presentations and documents explaining this agile method, but I still don't know exactly what a requirement should be

And who has the authority to decide? Edit: Apparently I haven't succeeded in formulating my question well. I am not asking how Java's argument passing works. I know that what looks like a variable hol

SDK: What is it exactly? How it could be useful? Is it necessary for a developer? Thanks

What is exactly the off-by-one errors in the while loop?how do i figure it out and how to fix it? Thanks

Here we have the description of isRegularFile() method of the BasicFileAttributes interface: Tells whether the file is a regular file with opaque content. What do they mean by opaque content, not

Currently been experimenting with using grunt and i'm gonna used grunt-contrib-qunit and it seems like it requires grunt-contrib-connect. What i am really confused about is that grunt-contrib-connect

Is byte code an intermediate form of code between assembly code and machine code? And is bytecode the same as object code? This is what I think - High level language->Assembly language->Machine

I have started reading and trying maven since yesterday. But its making me go crazy. I am java developer but never came across ant or maven before. I want to know what exactly happens with the depende

What exactly does the stop color % mean in css3 gradient? Good example would be great..

I use delegates (Actions, WaitCallbacks, Funcs) quite often but I am trying to get a better understanding of exactly 'what' they are. I have a fairly good understanding of objects vs reference types,

I am trying to understand what exactly is going on in the background. Given the simplified Model of an Inverted Index (forget about positions and scores): For each word there is a sorted list of docum

I have no experience with .NET Entity Framework and I have to understand what exactly do this Entitity Framework query and translate in in classic SQL (for Microsoft SQL server) So I have this query:

I am learning the REST architecture these days. I have developed many small small projetcs using jersey. My question is what exaclty is JAX_RS ? I understand that JAX-RS is a set of interfaces (all th

What does a Web service really mean ? I am not looking for a theoretical explanation, I am looking for something practical. I was thinking that anything I can call from an external client is a Web ser

Presuming that I don't know the name of my base node or its children, what is the XPath syntax for all nodes exactly one below the base node? With pattern being an XmlNode, I have the following code

I have been trying to figure out, what exactly a inbound end point and outbound end point. For me it is bit of an eluding to understand. what are exactly inbound and outbound endpoints for/do in mule

I am a little bit confused about what Apache Karaf exactly is. Can you say that Apache Karaf includes, amongst other things: Apache Felix (which is an implementation of the OSGi 4.2 framework) Apache

My colleague mentioned that there are some major improvements in CLR 4.0 related to Event Tracing for Windows but I couldn't find details of what exactly is new. There are few blog posts that mention

My company is always having problems with software not working because run-times or missing. I hear people say this a lot (you need the 32-bit run times, Microsoft run-times, etc etc). What exactly

What is getContext() method and what is drawing context exactly? why we always pass the string 2d to the getContext() method?

I have been doing Java SE for some years now and moving on to Java EE. However I have some trouble understanding some aspects of Java EE. Is Java EE just a specification? What I mean is: Is EJB Java

I`m new to write c code for ODBC but here I have question... after searching for the tutorial for odbc function tutorials for C, I still caanot get exactly how they work collaborately... what does the

MSDN states WebRequest.Timeout means The length of time, in milliseconds, until the request times out, or the value Timeout.Infinite to indicate that the request does not time out. What exactly cons

I just started learning Ruby on rails and I was wondering what Heroku really is? I know that its a cloud that helps us to avoid using servers? When do we actually use it? Thank you!