Do I remember correctly that given a computer and a program, it is always possible in theory for another computer to determine whether the first computer will come to a halt at some point in running that first program? Or am I remembering exactly the opposite of what is the case?
I should just go look it up.
-FrL-
I expect this is what you refer to:
A Turing machine is a simple computational device with an infinite length of ‘tape’ to store data on. The tape is split into a series of cells, like frames on a reel of film. It can move the tape forward or backward one cell at a time.
…
Turing wondered whether it would be possible to write a Turing machine program that would take two inputs:
A Turing machine program P, and
some input for program P
and would give as its output the answer to the question whether a Turing machine executing program P would ever halt on that input.
That’s roughly what I’m talking about, but what I was wondering is this. Even given the fact that no general halting algorithm can be constructed, still, given a particular program P, can it definitely be decided about P at least in theory whether it will halt?
-FrL-
Nope. If you could do this, you could solve the general halting problem by implementing a program that generates the P-specific solution for each P. Since we know the general halting problem to be undecidable, it follows that the generation of P-specific solutions itself must be undecidable (for at least some P).
It’s not immediately obvious to me that the P-specific solution is computable from P. Is it?
Would I be correct in saying that the halting problem is, in fact, semidecidable? After all, I could write an algorithm like this:
input a program P
run P
output “HURRAH! THE PROGRAM HALTS!”
My algorithm will always correctly detect programs that do eventually halt. Of course, you’ll get no answer if the program doesn’t halt, but that’s only required for full decidability.
Is my understanding of semidecidability correct? If so, are there any examples of problems out there that aren’t even semidecidable?
A problem like that is said to be recursively enumerable, and yes, there are problems that are not recursively enumerable. For instance, the complement of the halting problem is not recursively enumerable.
The problem with this sort of scheme is: Without arbitrary timeouts, how do you know the difference between a program that never halts and one that will halt after a thousand years?
No, that’s the point I was trying (badly) to make. I interpreted the OP’s question as “given P, is there a procedure we can use to generate an algorithm that answers halt(P).” I make the assumption that procedure generatability=computability, but I think I’m pretty safe there.
If you could do this for any P, you could solve the halting problem. Therefore you can’t do it for at least some P.
The question: “for any P, can we come universally produce an algortihm noncomputationally?” isn’t answered by this, but I don’t know what it means, either.
Turing showed that there are specific programs that do not halt, but it is impossible to prove that they do not halt. Obviously, no such program can be explicitly known. Just as obvious, if a program does halt, then there is a simple proof: run it and it will halt (not necessarily before the entropy death of the universe, however).
The idiotic error that Roger Penrose made (in “The Emperor’s New Mind”) was in not realizing that you cannot know that a program is not halting if its halting problem is unsolvable. Obvously, some non-halting program are known to be non-halting. For example, the BASIC program
10 goto 10
Well obviously my little algorithm has no practical use whatsoever, but this is computability theory after all. 
Anyway, I just took a look at Wikipedia and found out that a problem is *co-*recursively enumerable if its complement is recursively enumerable. So the halting problem is recursively enumerable, and the co-halting problem is co-recursively enumerable. (I don’t know if “co-halting problem” is generally accepted terminology but I reckon it sounds cool.)
Are there any problems that are neither recursively nor co-recursively enumerable?
(Sorry for hijacking your thread, Frylock, but hopefully you’re finding this interesting. If not, feel free to butt back in with your own questions.)
Actually, I was asking “Given any particular P, is there necessarily an algorithm that answers halt(P)?”
I’m starting to think the question is illformed in some way, though. You could answer with a trivial “yes” by pointing the “algorithm” that simply spits out a “yes” no matter what “answers” halt(P)" for every P that halts. Similarly for an algorithm that just spits out a “no.”
-FrL-
I want to say that { 1x | x is a member of the halting problem } [symbol]È[/symbol] { 0y | y is not a member of the halting problem } is neither r.e. nor co-r.e., but I can’t find a reference for that.
As TimeWinder explained, if the answer to this question is “yes”, then you can solve the halting problem. The snag is that you need to be able to compute that algorithm, and I’m pretty sure you can. You need to modify the algorithm slightly so that it will spit out three possible returns: 0 if the program P is not the program decided by this algorithm, 1 if it is and it halts, and 2 if it is and it does not halt. Then you can just run all of the halting-detection algorithms on P until one of them returns something other than 0. There’s your answer.
…I think that works. Anyone see any issues with the modifications?
EDIT: I don’t think that works. The problem is in being able to encode all of the halting detection programs into one finite-length program. Neat idea, though.
For every program, there exists an algorithm which will determine whether that program will halt. The algorithm is very simple: In fact, a mere two algorithms will, between them, work for all programs.
For instance, for the program
10 Goto 10
the algorithm is
print “The program does not halt”
And for the program
10 End
the algorithm is
print “The program halts”
The kicker, of course, is in determining which algorithm is the correct one to use for any given program.
One other caveat: Turing’s original theorem was cast in terms of machines with unlimited memory. If, on the other hand, you have a program and a computer with finite memory, then another computer with more memory (a little more than twice as much would do it) can, in fact, determine whether the program will halt on the first computer (though it might take a very long time to determine).
Finally, it might be helpful to realize that almost any problem in number theory can be cast as a halting problem. For instance, the Goldbach Conjecture. I could write a program which steps through every even number, and for each one, it checks all of the prime numbers up to half that number. If it finds a pair of primes that add up to the number, it steps up to the next even number, and if it doesn’t, then it outputs the number and exits. If I had a way to tell if a program would terminate, I could use it on that Goldbach program, and the output of my determiner would then tell me whether Goldbach’s conjecture is true. Similarly, for most other number theory problems. So if there exists an unsolvable number theory problem, then the halting problem must also be unsolvable.
Right, in my post number 12 here I came to that realization.
This is pretty much what I was after in the poorly-phrased OP. But what does “determine” mean here?
-FrL-
And that’s the $65,536 question. As other posters have pointed out, on a real computer (finite memory), the answer is “yes” (and in fact HALT() is solvable), because that case reduces to a state machine: there are finitely many (albeit a huge number) possible memory states, and the transitions between them are known. You can simply “execute” the program until you either halt or return to a state you’ve been in before – and you’re guaranteed to do that in an equally finite number of steps at most. (We’ll ignore external inputs at the point, but it actually doesn’t change the problem much.)
In the infinite memory case, the problem is much harder. The question “is there an algorithm for XXXX?” is the root of many of the great unsolved problems of computer science. In particular, the P=NP debate basically boils down to an algorithm existence problem: “Does there exist a polynomial time algorithm for computing this thing I know how to do in non-deterministic polynomial time?”
My gut feeling is that the answer to the question at the top of this post is “no.” In fact, I’m almost sure of it. But a proof doesn’t leap immediately to mind–I’ll keep thinking.
Who needs gut feelings, here? Turing already settled the question decades ago. There is no algorithm executable on any Turing machine or the equivalent which, given an arbitrary Turing machine program as input, can always determine whether the program halts or not. There are of course some programs for which the question can be answered, of course, but there are also some programs for which it cannot be.
If you want an intuitive proof (not as rigorous as a true proof, of course, but one could make it so) of Turing’s theorem, you can construct one from a varient of the Berry paradox. Suppose you have an algorithm, of length N bits, which can solve the halting problem for an arbitrary input program. Then you could include that in some other master program, of length not much more than N (let’s say the length of your program is M), which systematically looks at every program of length M or less, determines whether it will halt, and then (if it halts) runs that program as a subroutine to find out what it outputs. It then takes the set of all of the positive integers output by all those programs, and finds the smallest positive integer which is not output by any of them, and then outputs that integer. So our master program is now outputting a number, call it X, which is not output by any program of length M bits or less. But our master program is itself a program of length M bits or less, and so there is, in fact, a program of M bits or less which outputs X. So we have a contradiction, and so our assumption must be false, and there is no algorithm which can always determine whether an arbitrary program will halt.
But that does not address the question of the OP.
-FrL-
“determine” means “decide”. For various reasons, it’s convenient to look at problems as a collection of binary strings, and to call such a collection a language L. A program P decides a language L iff P(x) = 1 whenever x is an element of L, and 0 otherwise.
Yes, but that’s just the halting problem. He’s asking something subtly different: Given a program P, does there exist an algorithm (specific to P, and whether or not we know how to find it), that answers halt(P) (only)? It seems that it’s possible for the answer to this question to be “yes,” even thought the halting problem tells us it’s not possible to use a single algorithm for all programs; it’s possble that “finding” the algorithm for P is nonomputable, even though the algorithm does exist.
In the degenerate case mentioned by a poster above, for example, an algorithm that prints “yes” and one that prints “no” covers the cases–and both are highly computable. What’s not computable is which one to use.