Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I just ran across an answer to another question that references the Halting Problem. He starts with this snippet:

def halts( code_block ):
    # Some magical code

def whistler():
    while halts(whistler): 
        sys.whistle( 1 )

and then explains how the routine halts cannot be defined correctly because it essentially ends up being logically equivalent to "this sentence is false". Aside from the Python-style syntax, this is basically the standard explanation of the halting problem, and I've never understood the concept. Every time I look at that type of example, I think "but why in the world would anyone approach the problem in that way in the first place?"

If I wanted to determine a difficult property of a piece of code, such as answering the question of whether or not it halts, there's no way I would put the analysis inside the code to be analyzed! First off, that leads to contradictions like this example, and second, adding analysis code changes the nature of the thing being analyzed. I would almost certainly go about looking for the answer to the question with external tools, not internal ones.

So yes, I understand that there's no way to write a correct implementation of halts in the example above. But let's restrict ourselves solely to the realm of code that actually can be written correctly, instead of hypotheticals. What's an example of code that can actually be written and executed, for which it is impossible to determine by external analysis whether the code will end up in an infinite loop or whether it will terminate?

share|improve this question
1  
function foo(){if (Math.random() < 0.5) while (true);} foo();? –  zzzzBov Jun 7 '11 at 1:24
    
@zzzzBov: This can be predicted easily enough if you know the state of the PRNG that Math.random implements. ;) –  Mason Wheeler Jun 7 '11 at 2:04
    
Why not start with en.wikipedia.org/wiki/Liar_paradox? –  Job Jun 7 '11 at 2:29
    
There are counting arguments that may be simpler to understand, although they require proofs by contradiction too. -- To get what you want, you'd need a program that is equivalent to solving an independent mathematical problem, such as the continuum hypothesis. But think about it this way: Many open problems in mathematics can be stated as programs that may or may not halt: Showing if it halts or not would be the same as solving a long standing problem in mathematics! –  Macneil Jun 7 '11 at 3:16

4 Answers 4

Every time I look at that type of example, I think "but why in the world would anyone approach the problem in that way in the first place?"

If I wanted to determine a difficult property of a piece of code, such as answering the question of whether or not it halts, there's no way I would put the analysis inside the code to be analyzed!

The trick here is that this is a proof by contradiction : assume A, demonstrate it would imply a paradox, conclude assumption was wrong.

So the idea is not that we "would approach the problem in that way" or that we "would put the analysis inside the code to be analyzed". The idea is rather: suppose someone came up with a program and said "Look, I wrote a program that tell if any given program will halt or not". "Oh really? Lemme see what happens if I plug it into itself?" KABOOM!

There's no need to actually take an existing example: this already proves there's no way such a program could exist.

On a side note, it does not mean we cannot try to write such a halts function. It just means it is impossible to write a halts function that will work for any program.

share|improve this answer
1  
"…it is impossible to write a halts function that will work for any program." In my opinion, that crucially important any is thoroughly under-emphasised in descriptions of the Problem. I'd even go so far as to wager you could write a halts() that works for the majority of programs. –  Jon Purdy Jun 7 '11 at 5:05
1  
I wouldn't go that far, but yes, there are branches of code you could definitely write a checking code for. I heard there are softwares doing that, with a "is ok" / "is ko" / "cannot tell" coloring for instance. –  Julien Guertault Jun 7 '11 at 5:52

If I wanted to determine a difficult property of a piece of code, such as answering the question of whether or not it halts, there's no way I would put the analysis inside the code to be analyzed! [...] I would almost certainly go about looking for the answer to the question with external tools, not internal ones.

If Turing's halting problem is really analogous Gödel's incompleteness theorems... then I think what it's really telling you is that you can never solve the problem without going to that external "layer" of meaning or representation.

Thus you cannot make an analyzer that works on itself, you can only make a meta-analyzer, and a meta-meta-analyzer for that, and a meta-meta-meta-analzyer for that, etc. (And you can't make reciprocal analyzers either.)

That's why the "nesting" is part of the problem.

share|improve this answer
    
That is indeed the point. A "simple" Turing complete language cannot decide halting. A "higher-order" logical language is required. And in some cases, the halting proofs are quite subtle. –  S.Lott Jun 7 '11 at 0:36

What's an example of code that can actually be written and executed, for which it is impossible to determine by external analysis whether the code will end up in an infinite loop or whether it will terminate?

The Collatz Conjecture, sometimes called the Syracuse Problem. http://en.wikipedia.org/wiki/Collatz_conjecture

Simple, and undecidable.

Need more? Here's a big list of problems you could write potentially correct algorithms for. Without a proof that your algorithm terminates, however, you don't ever really know if it's correct.

http://en.wikipedia.org/wiki/List_of_undecidable_problems

share|improve this answer
2  
Actually, the conjecture may have been recently proved true by Gerhard Opfer, a former student of Collatz. –  Jon Purdy Jun 7 '11 at 0:54
    
@Jon: thanks for the exciting news –  kevin cline Jun 7 '11 at 4:59

You are stating the answer to your question without realizing it.

So yes, I understand that there's no way to write a correct implementation of halts in the example above. But let's restrict ourselves solely to the realm of code that actually can be written correctly, instead of hypotheticals.

This is the essence of the halting problem. There is no way to write the halts function. There is no #some magical code. It cannot exist. The proof of the halting problem is a restriction on the realm of code that can be written.

What's an example of code that can actually be written and executed, for which it is impossible to determine by external analysis whether the code will end up in an infinite loop or whether it will terminate?

This is another important distinction to make. The halting problem says it is not possible to write a program that determines if any program will halt.

It is possible to write a program that determines if a particular program halts.

share|improve this answer
    
"It is possible to write a program that determines if a particular program halts" while I agree with the idea, stating it that way is a bit misleading, since there are particular programs for which it is impossible to do. –  Julien Guertault Jun 7 '11 at 5:47
    
@Julien Good clarification, thanks. –  David Jun 7 '11 at 12:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.