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 was just reading another explanation of the halting problem, and it got me thinking all the problems I've seen that are given as examples involve infinite sequences. But I never use infinite sequences in my programs - they take too long. All the real world applications have lower and upper bounds. Even reals aren't truly reals - they are approximations stored as 32/64 bits etc.

So the question is, is there a subset of programs that can be determined if they halt? Is it good enough for most programs. Can I build a set of language constructs that I can determine the 'haltability' of a program. I'm sure this has been studied somewhere before so any pointers would be appreciated. The language wouldn't be turing complete, but is there such a thing as nearly turing complete which is good enough?

Naturally enough such a construct would have to exclude recursion and unbounded while loops, but I can write a program without those easily enough.

Reading from standard input as an example would have to be bounded, but that's easy enough - I'll limit my input to 10,000,000 characters etc, depending on the problem domain.

tia

[Update]

After reading the comments and answers perhaps I should restate my question.

For a given program in which all inputs are bounded can you determine if the program halts. If so what are the constraints of the language and what are the limits of the input set. The maximal set of these constructs would determine a language which can be deduced to halt or not. Is there some study that's been done on this?

[Update 2]

here's the answer, it's yes, way back in 1967 from http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

That the halting problem can be at least theoretically solved for finite-state systems has been already argued by Minsky in 1967 [4]: “...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine...”

(and so if you stick to finite turing machines then you can build an oracle)

share|improve this question
12  
"infinite sequences... take too long". Made me laugh out loud. –  Bryan Oakley Dec 19 '11 at 3:35
    
scienceblogs.com/goodmath/2008/12/… - This wouldn't be the post read in question? –  World Engineer Dec 19 '11 at 3:38
3  
I believe SQL92 and Regular Expressions are examples of languages that are guaranteed to halt. –  Elian Ebbing Dec 19 '11 at 13:24
2  
Please post "Update2..." as an answer. –  S.Lott Dec 19 '11 at 16:38
2  
You do not need to exclude recursion. If you limit the recursion to strict sub-terms of the callee arguments you'll always be able to prove termination. It is a sufficient requirement - no "bounded loops" and alike are necessary, as long as you're using the Church numerals. –  SK-logic Dec 20 '11 at 11:49

8 Answers 8

up vote 4 down vote accepted

The issue isn't on the input (obviously, with unbounded input, you can have unbounded running time just to read the input), it is on the number of internal states.

When the number of internal state is bounded, theoretically you can solve the halting problem in all cases (just emulate it until you reach halting or the repetition of a state), when it isn't, there are cases where it isn't solvable. But even if the number of internal states is in practice bounded, it is also so huge that the methods relying of the boundedness of the number of internal states are useless to prove the termination of any but the most trivial programs.

There are more practical ways to check the termination of programs. For instance, express them in a programming language which hasn't recursion nor goto and whose looping structures have all a bound on the number of iterations which has to be specified on entry of the loop. (Note that the bound hasn't to be really related to the effective number of iterations, a standard way to prove the termination of a loop is to have a function which you prove is strictly decreasing from one iteration to the other and your entry condition ensure is positive, you could put the first evaluation as your bound).

share|improve this answer

First off, consider what would happen if we had a halting detector. We know from the diagonal argument that there exists at least one program that would cause a halting detector to either never halt or give a wrong answer. But that's a bizarre and unlikely program.

There is another argument though that a halting detector is impossible, and that is the more intuitive argument that a halting detector would be magical. Suppose you want to know if Fermat's Last Theorem is true or false. You just write a program that halts if it is true and runs forever if it is false, and then run the halting detector on it. You don't run the program, you just run the halting detector on the program. A halting detector would enable us to immediately solve a huge number of open problems in number theory just by writing programs.

So, can you write a programming language that is guaranteed to produce programs whose halting can be always determined? Sure. It just cannot have loops, conditions and use arbitrarily much storage. If you're willing to live with no loops, or no "if" statements, or a strictly restricted amount of storage, then sure, you can write a language whose halting is always determinable.

share|improve this answer
1  
One can have the if statement if the jump always has to be forward, never backwards. I am thinking of a restricted subset of BASIC language, where "GOTO X" means go to the line number currentLine + X, and X must be greater than 0. If the line is invalid, then halt. This would up the storage demands, but would allow for some non-trivial logic. This is probably equivalent to a finite state machine where the vertices form a graph and that graph may not have any cycles, or else the FSM is invalid. Also, any state that is a dead end must be an accepting state. –  Job Dec 19 '11 at 3:56
3  
it could have bounded loops - for i=1 to 10 for example, likewise well behaved iterators. So is there a class of finite problems that can be solved - fermats theorem is again involved in the infinite sequence of reals. But if we restrict the domain to numbers less than 1 000 000 then it does halt. –  daven11 Dec 19 '11 at 4:51
2  
Why not conditions? It seems that conditions without jumps can be shown to always halt... –  Billy ONeal Dec 19 '11 at 5:41
2  
@nikie: Of course it is a weak argument. The point is that such a halting detector would be able to prove or disprove such statements without necessarily finding the proof. The intuition that I'm intending the reader to develop here is that a language for which a trivial halting detector could be written is a language that cannot represent even simple problems in number theory like Fermat's Last Theorem or Goldbach's Conjecture, and therefore probably is not a very useful language. –  Eric Lippert Dec 19 '11 at 15:12
2  
@EricLippert: Wrong. Such a language will have loops, proper storage and many other useful things. It is possible to code almost anything in it. Behold, here it is: coq.inria.fr –  SK-logic Dec 20 '11 at 11:29

is there a subset of programs that can be determined if they halt?

Yes.

Is it good enough for most programs?

Define "most".

Can I build a set of language constructs that I can determine the 'haltability' of a program?

Yes.

is there such a thing as nearly turing complete which is good enough?

Define "nearly".

Many folks write Python without using while statement or recursion.

Many folks write Java using only the for statement with simple iterators or counters that can be trivially proven to terminate; and they write without recursion.

It's pretty easy to avoid while and recursion.


For a given program in which all inputs are bounded can you determine if the program halts?

No.

If so what are the constraints of the language and what are the limits of the input set.

Um. The Halting problem means the program can't ever determine things about programs as complex as itself. You can add any one of a large number of constraints to get past the halting problem.

The standard approach to the halting problem is to allow proofs using a slightly "richer" set of mathematical formalisms than are available in the programming language.

It's easier to extend the proof system than it is to restrict the language. Any restriction leads to arguments for the one algorithm that's difficult to express because of the restriction.

The maximal set of these constructs would determine a language which can be deduced to halt or not. Is there some study that's been done on this?

Yes. It's called "Group Theory". A set of values closed under a set of operations. Pretty well understood stuff.

share|improve this answer
    
"nearly" is the bit I'm asking. Is there are finite class of problems for which a program can be said to halt and how limited is the problem set? For instance the statement if(i<10) then print(i) does halt for all i. If I restrict the domain of i to 32 bit integers then it too halts. –  daven11 Dec 19 '11 at 4:54
    
Keep in mind a for loop is a while loop, and people often put more complicated things in the condition term than just x < 42. –  Billy ONeal Dec 19 '11 at 5:38
    
@BillyONeal: Good point. In Python a for loop is very, very tightly constrained to work through an iterator. A more general for loop in Java, however, can include extra conditions that invalidate simple use of an iterator. –  S.Lott Dec 19 '11 at 14:11
    
"Is there are finite class of problems for which a program can be said to halt?" The answer remains yes. "how limited is the problem set?" Um. Finite is finite. If you give up on trying to approximate real numbers and stick to natural numbers, closed under all mathematical operations, you're doing ordinary group theory. Modular arithmetic. Nothing special. It's not clear what you're asking. Are you asking what modular arithmetic is? –  S.Lott Dec 19 '11 at 14:15
    
@S.Lott I mean numbers as represented in a machine, not numbers in the abstract sense. So think of numbers as a fixed number of bits. These numbers have slightly different rules from the integers and reals. Hope that makes sense. –  daven11 Dec 19 '11 at 22:50

For every program that works on a limited amount of memory (including storage of all kind), the halting problem can be solved; i.e. an undecidable program is bound to take more and more memory on the run.

But even so, this insight doesn't mean that it can be used for real-world problems, since a halting program, working on just a few kilobytes of memory, can easily take longer than the remaining lifetime of the universe to halt.

share|improve this answer

To (partially) answer your question "Is there a subset of programs that avoid the halting problem": yes, in fact there is. However, this subset is amazingly useless (note that the subset I'm talking about is a strict subset of the programs that halt).

The study of the complexity of problems for 'most inputs' is called generic-case complexity. You define some subset of the possible inputs, prove that this subset covers 'most inputs' and give an algorithm that solves the problem for this subset.

For instance, the halting problem is solvable in polynomial time for most inputs (in fact, in linear time, if I understand the paper correctly).

However, this result is rather useless because of three side notes: firstly, we talk about Turing machines with a single tape, rather than real-world computer programs on real-world computers. As far as I know, no one knows whether the same holds for real-world computers (even though real world computers may be able to compute the same functions as Turing machines, the number of allowed programs, their lengths and whether they halt may be completely different).

Secondly, you have to watch out what 'most inputs' means. It means that the probability that a random program of 'length' n can be checked by this algorithm tends to 1 as n tends to infinity. In other words, if n is large enough, then a random program of length n can almost surely be checked by this algorithm.

Which programs can be checked by the approach described in the paper? Essentially, all programs that halt before repeating a state (where 'state' roughly corresponds to a line of code in a program).

Even though nearly all programs can be checked in this way, none of the programs that can be checked in this way are very interesting and they usually won't be designed by humans, so this is of no practical value whatsoever.

It also indicates that generic-case complexity will probably not be able to help us with the halting problem, as nearly all interesting programs are (apparently) hard to check. Or, alternatively phrased: nearly all programs are uninteresting, but easy to check.

share|improve this answer
2  
-1, This is wrong on so many levels... –  user281377 Dec 19 '11 at 20:19
1  
First, real-worlds computers cannot compute anything that a Turing machine can't. Till now, nobody has shown a real-world computer more capable (in terms of computablity) than a Turing machine. Second, if a program repeats it's state, it won't halt, so the halting problem is solved for that program and input. Remember: The halting problem is about deciding whether or not a program will halt on given input. An infinite loop is ok once you positively detect it. Finally: There is a large set of useful programs for which the halting problem is solvable: Those operating on limited storage. –  user281377 Dec 19 '11 at 20:26
    
As for your first issue: as remarked in the paper, showing that some model of computation is Turing complete does not preserve how many programs exactly halt, so the result they prove does not immediately mean anything for other models of computation. I'm well aware of Turing completeness, and I'm not completely sure why it makes my answer 'wrong'. –  Alex ten Brink Dec 19 '11 at 21:50
    
As for your second issue: the states I'm talking about is not the same as the 'state of a machine' one usually talks about (which involves the state of everything that can have state), but rather the state the finite state automaton used to control the Turing machine is in, which roughly corresponds to the line of code a program is working on at any point during execution. On repeating a line of code the contents of your memory may be different, so this does not immediately imply halting at all. I'll update my answer to make this more clear. –  Alex ten Brink Dec 19 '11 at 21:51
    
@ammoQ: No, the halting problem is not solvable if you are talking about real-world systems with limited storage, as that would mean building a real-world system that can handle combinations of states. As the number of possible register states in most CPUs exceeds the number of atoms in the Universe, you aren't going to be able to do that. –  David Thornley Dec 19 '11 at 22:52

I recommend you to read Gödel, Escher, Bach. It's a very fun and illuminating book that, among other things, touches on Gödel's incompleteness theorem and the halting problem.

To answer your question in a nutshell: the halting problem is decidable as long as your program does not contain a while loop (or any of its many possible manifestations).

share|improve this answer
    
Sorry, I misread you. I deleted my comment but I'll restate the recommendation of GEB. –  AProgrammer Dec 19 '11 at 14:17
    
@zvrba That's been on my reading list for some time - probably time to dive in. –  daven11 Dec 19 '11 at 22:28

here's the answer, it's yes, way back in 1967 from http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

That the halting problem can be at least theoretically solved for finite-state systems has been already argued by Minsky in 1967 [4]: “...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine...”

(and so if you stick to finite turing machines then you can build an oracle)

Of course how long this takes is another question

share|improve this answer

There is, and in fact there are programs in real life that solve the halting problem for other problems all the time. They are part of the operating system you are running your computer on. Undecidability is a weird claim that only says that there isn't such a program that works for ALL other programs.

One person correctly stated that the halting proof seems to be the only program for which it cannot be solved, as it infinitely traces itself like a mirror. This same person also stated that if there was a halting machine, it would be magic because it would tell us hard math problems by telling us ahead of time if it's solver algorithm would halt.

The assumption in both of these cases is that the halting machine doesn't trace because there is no proof that it traces. However, in reality it actually does trace/ run the program it is run on with the input given.

The logical proof at least is simple. If it didn't need to trace at least the first step, it wouldn't need the input along with the program it's run on. In order to make any use of the information, it has to at least trace the first step before trying to analyze where that path is going.

The hard math problems mentioned in the top answer are ones where you cannot fast forward to figure out the answer, which means the halting problem would have to continue tracing until some pattern was recognizable.

So the only practical argument to get from the halting problem is that a halting machine can't determine the outcome of an optimized problem solver faster than the problem solver can finish.

Giving a formal proof for this reasoning is harder, and although I believe I could, attempting to explain it to anyone an academia will result in them throwing an ape like temper-tantrum and swinging from the chandelier. It's best just not to argue with those people.

share|improve this answer

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.