## digitalmars.D - [Theory] Halting problem

- %u <e ee.com> Oct 09 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Oct 09 2010
- %u <e ee.com> Oct 09 2010
- Norbert Nemec <Norbert Nemec-online.de> Oct 10 2010
- Justin Johansson <no spam.com> Oct 10 2010
- %u <e ee.com> Oct 10 2010
- Norbert Nemec <Norbert Nemec-online.de> Oct 10 2010
- %u <e ee.com> Oct 10 2010
- Norbert Nemec <Norbert Nemec-online.de> Oct 10 2010
- %u <e ee.com> Oct 10 2010
- Norbert Nemec <Norbert Nemec-online.de> Oct 12 2010
- BCS <none anon.com> Oct 12 2010
- %u <e ee.com> Oct 12 2010
- Stewart Gordon <smjg_1998 yahoo.com> Oct 12 2010
- Stewart Gordon <smjg_1998 yahoo.com> Oct 12 2010
- %u <e ee.com> Oct 12 2010
- Stewart Gordon <smjg_1998 yahoo.com> Oct 13 2010
- %u <e ee.com> Oct 13 2010
- "Manfred_Nowak" <svv1999 hotmail.com> Oct 13 2010
- Stewart Gordon <smjg_1998 yahoo.com> Oct 13 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> Oct 13 2010

Just to be clear about this, the halting problem is only unsolvable for Turing machines. That is, a machine with a tape that extends or is indefinitely extensible to the right.[wikipedia:Turing machine] In the more general limited-memory setup it is actually quite simple to solve the Halting problem: 1. Save every state of the system. 2. If the program ends, the program Halts -> done. 2. For every state, check to if it has been saved before. If so, the program loops -> done. 3. Wait until all states are saved, the program Halts -> done. Simple in theory that is :)

Oct 09 2010

%u <e ee.com> wrote:Just to be clear about this, the halting problem is only unsolvable for Turing machines. That is, a machine with a tape that extends or is indefinitely extensible to the right.[wikipedia:Turing machine] In the more general limited-memory setup it is actually quite simple to solve the Halting problem: 1. Save every state of the system. 2. If the program ends, the program Halts -> done. 2. For every state, check to if it has been saved before. If so, the program loops -> done. 3. Wait until all states are saved, the program Halts -> done. Simple in theory that is :)

Of course. However, for non-trivial programs it is hard enough that we may consider it impossible. -- Simen

Oct 09 2010

== Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article%u <e ee.com> wrote:Just to be clear about this, the halting problem is only unsolvable for Turing machines. That is, a machine with a tape that extends or is indefinitely extensible to the right.[wikipedia:Turing machine]

Of course. However, for non-trivial programs it is hard enough that we may consider it impossible.

This may be, but too often I see the theoretical(truly impossible) problem mentioned when the practical Halting problem is applicable. Especially people asking about the Halting problem should not be thrown off by saying that the theoretical Halting problem is why a problem can't be implemented. Why, for instance, doesn't Stewart Gordon's proof not apply for finite memory programs?

Oct 09 2010

"Impossible to solve" is often used synonymous to "exponentially hard to solve" meaning, as the problem size (e.g. size of finite memory) grows as N, the cost for solution grows as exp(N). Of course, the actual cost of an actual problem always depends on the pre-factor, but experience shows that exponentially hard problems are typically only solvable for trivially small problems. On 09/10/10 21:59, %u wrote:== Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article%u<e ee.com> wrote:Just to be clear about this, the halting problem is only unsolvable for Turing machines. That is, a machine with a tape that extends or is indefinitely extensible to the right.[wikipedia:Turing machine]

Of course. However, for non-trivial programs it is hard enough that we may consider it impossible.

This may be, but too often I see the theoretical(truly impossible) problem mentioned when the practical Halting problem is applicable. Especially people asking about the Halting problem should not be thrown off by saying that the theoretical Halting problem is why a problem can't be implemented. Why, for instance, doesn't Stewart Gordon's proof not apply for finite memory programs?

Oct 10 2010

On 10/10/2010 8:07 PM, Norbert Nemec wrote:"Impossible to solve" is often used synonymous to "exponentially hard to solve" meaning, as the problem size (e.g. size of finite memory) grows as N, the cost for solution grows as exp(N). Of course, the actual cost of an actual problem always depends on the pre-factor, but experience shows that exponentially hard problems are typically only solvable for trivially small problems.

That's a fair observation. Cheers Justin Johansson

Oct 10 2010

I am not sure where exactly the line lies where people tend to use impossible as a synonym for a hard problem, but I agree that np might well be around that border. It depends on "trivial", but I wouldn't call integer factorization impossible. The point I was trying to make was that using "impossible" to denote the practical halting problem is very confusing as the theoretical Halting problem is truly impossible. Confusing, as the proof at first sight seems to hold on memory limited systems as well. == Quote from Norbert Nemec (Norbert Nemec-online.de)'s article"Impossible to solve" is often used synonymous to "exponentially hard to solve" meaning, as the problem size (e.g. size of finite memory) grows as N, the cost for solution grows as exp(N). Of course, the actual cost of an actual problem always depends on the pre-factor, but experience shows that exponentially hard problems are typically only solvable for trivially small problems. On 09/10/10 21:59, %u wrote:== Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article%u<e ee.com> wrote:Just to be clear about this, the halting problem is only unsolvable for Turing machines. That is, a machine with a tape that extends or is indefinitely extensible to the right.[wikipedia:Turing machine]

Of course. However, for non-trivial programs it is hard enough that we may consider it impossible.

This may be, but too often I see the theoretical(truly impossible) problem mentioned when the practical Halting problem is applicable. Especially people asking about the Halting problem should not be thrown off by saying that the theoretical Halting problem is why a problem can't be implemented. Why, for instance, doesn't Stewart Gordon's proof not apply for finite memory programs?

Oct 10 2010

On 10/10/10 17:06, %u wrote:I am not sure where exactly the line lies where people tend to use impossible as a synonym for a hard problem, but I agree that np might well be around that border. It depends on "trivial", but I wouldn't call integer factorization impossible. The point I was trying to make was that using "impossible" to denote the practical halting problem is very confusing as the theoretical Halting problem is truly impossible. Confusing, as the proof at first sight seems to hold on memory limited systems as well.

I think, the essence here is the "limited memory" issue. A turing machine has infinite memory available, but a program that finished in finite time will always have used only a finite amount of memory. The halting problem is to determine if a program written down as a finite piece of code will finish in finite time and finite memory or not. In language design, the theoretical halting problem actually is often an argument because the compiler does not know the memory limitation at run time. The finite memory of the machine can therefore not be used to reason about a piece of code. For the purpose of the compiler, the machine has to be assumed to have arbitrarily much (i.e. infinite) memory.

Oct 10 2010

== Quote from Norbert Nemec (Norbert Nemec-online.de)'s articleOn 10/10/10 17:06, %u wrote:I am not sure where exactly the line lies where people tend to use impossible as a synonym for a hard problem, but I agree that np might well be around that border. It depends on "trivial", but I wouldn't call integer factorization impossible. The point I was trying to make was that using "impossible" to denote the practical halting problem is very confusing as the theoretical Halting problem is truly impossible. Confusing, as the proof at first sight seems to hold on memory limited systems as well.

machine has infinite memory available, but a program that finished in finite time will always have used only a finite amount of memory. The halting problem is to determine if a program written down as a finite piece of code will finish in finite time and memory or not.

In language design, the theoretical halting problem actually is often an argument because the compiler does not know the memory limitation at run time. The finite memory of the machine can therefore not be used to reason about a piece of code. For the purpose of the compiler, the machine has to be assumed to have arbitrarily much (i.e. infinite) memory.

would be surprised to hear that they would think of the theoretical Halting problem where the practical halting problem as an argument would suffice. Programs generally can't index an infinite amount of memory. Why would they use an argument which rests on an abstract system where they could just as easily use an argument based on an actual system. Anyway, I made this thread because in uni I got the Halting problem explained in totally the wrong context and would like other people not to make the same wrong first step.

Oct 10 2010

On 10/10/10 19:36, %u wrote:== Quote from Norbert Nemec (Norbert Nemec-online.de)'s articleIn language design, the theoretical halting problem actually is often an argument because the compiler does not know the memory limitation at run time. The finite memory of the machine can therefore not be used to reason about a piece of code. For the purpose of the compiler, the machine has to be assumed to have arbitrarily much (i.e. infinite) memory.

would be surprised to hear that they would think of the theoretical Halting problem where the practical halting problem as an argument would suffice. Programs generally can't index an infinite amount of memory. Why would they use an argument which rests on an abstract system where they could just as easily use an argument based on an actual system.

Basically: because 1GB=infinity for all purposes of logical reasoning.Anyway, I made this thread because in uni I got the Halting problem explained in totally the wrong context and would like other people not to make the same wrong first step.

I know that situation very well: having the big Aha-effect after years of misunderstanding calls for telling people about it. Actually, I find it quite interesting to discuss this kind of issues once in a while.

Oct 10 2010

== Quote from Norbert Nemec (Norbert Nemec-online.de)'s articleOn 10/10/10 19:36, %u wrote:== Quote from Norbert Nemec (Norbert Nemec-online.de)'s articleIn language design, the theoretical halting problem actually is often an argument because the compiler does not know the memory limitation at run time. The finite memory of the machine can therefore not be used to reason about a piece of code. For the purpose of the compiler, the machine has to be assumed to have arbitrarily much (i.e. infinite) memory.

would be surprised to hear that they would think of the theoretical Halting problem where the practical halting problem as an argument would suffice. Programs generally can't index an infinite amount of memory. Why would they use an argument which rests on an abstract system where they could just as easily use an argument based on an actual system.

If you'd left out logical it would have been just fine :D I'm not even going to give ridiculous logical proof with this assumption.. no I will not.. .. assume inf is 1GB.. No! ..Anyway, I made this thread because in uni I got the Halting problem explained in totally the wrong context and would like other people not to make the same wrong first step.

of misunderstanding calls for telling people about it. Actually, I find it quite interesting to discuss this kind of issues once in a while.

Oct 10 2010

On 10/10/2010 09:16 PM, %u wrote:Basically: because 1GB=infinity for all purposes of logical reasoning.

If you'd left out logical it would have been just fine :D I'm not even going to give ridiculous logical proof with this assumption.. no I will not.. .. assume inf is 1GB.. No!

Sorry, my wording was extremely poorly chosen. What I meant was: if you start any logical reasoning based on the "finite state space" of a real computer, this approach is very likely to be of little practical value for a real world problem. More explicitely: a brute force solution of the halting problem is indeed theoretically possible for a finite machine, but it scales exponentially in the memory size, resulting in a run time which is large compared to anything that you could reasonably call "finite".

Oct 12 2010

Hello %u,Just to be clear about this, the halting problem is only unsolvable for Turing machines.

More correctly, the halting problem for machine X is unsolvable by machine X (or any weaker machine). -- ... <IXOYE><

Oct 12 2010

== Quote from BCS (none anon.com)'s articleHello %u,Just to be clear about this, the halting problem is only unsolvable for Turing machines.

X (or any weaker machine).

I was looking for a way out by making machine X allocate only 32b per program Except for halt.exe :D That way you can't create the program which loops if halt halts and is thus a way out of that argument :) But thanks, it is a much nicer definition.

Oct 12 2010

On 09/10/2010 18:58, %u wrote:Just to be clear about this, the halting problem is only unsolvable for Turing machines.

No, it's unsolvable for any computational class that's at least as powerful as a Turing machine. In its most general form, the unsolvability theorem states that, given a computational class X, no algorithm in X can correctly determine whether an arbitrary algorithm in X fed arbitrary input will halt. You can, however, consider a computational class X', a superset of X that includes a means of determining whether an arbitrary algorithm in X will halt. But no matter how powerful X' is, it will never be able to determine whether an arbitrary algorithm in X' will halt - you'll need X'' for that. There are a few esolangs designed around this principle which, sadly, we aren't likely to see implementations of any time soon. http://esoteric.voxelperfect.net/wiki/Brainhype http://esoteric.voxelperfect.net/wiki/Banana_Scheme Stewart.

Oct 12 2010

On 09/10/2010 18:58, %u wrote: <snip>In the more general limited-memory setup it is actually quite simple to solve the Halting problem: 1. Save every state of the system. 2. If the program ends, the program Halts -> done. 2. For every state, check to if it has been saved before. If so, the program loops -> done. 3. Wait until all states are saved, the program Halts -> done.

I get it now under the assumption that these aren't step-by-step instructions. But can this algorithm run within this limited-memory setup? I think not - by my calculation, to do it for a setup with n bits of memory, the halt analyser would need 2^n bits. Stewart.

Oct 12 2010

== Quote from Stewart Gordon (smjg_1998 yahoo.com)'s articleOn 09/10/2010 18:58, %u wrote: <snip>In the more general limited-memory setup it is actually quite simple to solve the Halting problem: 1. Save every state of the system. 2. If the program ends, the program Halts -> done. 2. For every state, check to if it has been saved before. If so, the program loops -> done. 3. Wait until all states are saved, the program Halts -> done.

instructions.

But can this algorithm run within this limited-memory setup? I think not - by my calculation, to do it for a setup with n bits of memory, the halt analyser would need 2^n bits. Stewart.

Yep, it needs to run in a minimal 2^n larger limited memory system (n2^n that is). But those two system could of course be on the same computer. My computer, for instance, can run Halt.exe on 30bit programs :D

Oct 12 2010

On 13/10/2010 00:23, %u wrote: <snip>Yep, it needs to run in a minimal 2^n larger limited memory system (n2^n that is). But those two system could of course be on the same computer. My computer, for instance, can run Halt.exe on 30bit programs :D

n2^n? Are you sure? Here's how I worked it out. Let P be the program being analysed, and H be the program that does the halt analysis. The only bits of information H needs to store are: - the code of P - the state P is in at the moment - whether P has so far visited each possible state The last of these is usually what takes up most of the space. If P is limited to n bits of memory, there are 2^n possible states. Whether a state has been visited is a boolean value, therefore we need only 2^n bits for the entire table. We don't need to store up the bit patterns of these states - which state each bit refers to is evident from its address in H's memory space. You could take this as meaning that the halting problem is solvable within a certain computational class: that in which a finite but arbitrarily large amount of memory must be allocated at the outset. However, we would need to allow the amount of memory to allocate to be a function of the input, which again leads to a problem: when you try to run H on itself, it will need more memory than itself, so the calculation would infinitely recurse. So essentially, two computational classes are involved: the one FOR which you are solving the halting problem, and the one IN which you are solving the halting problem. Stewart.

Oct 13 2010

== Quote from Stewart Gordon (smjg_1998 yahoo.com)'s articleOn 13/10/2010 00:23, %u wrote: <snip>Yep, it needs to run in a minimal 2^n larger limited memory system (n2^n that is). But those two system could of course be on the same computer. My computer, for instance, can run Halt.exe on 30bit programs :D

Here's how I worked it out. Let P be the program being analysed, and H be the program that does the halt analysis. The only bits of information H needs to store are: - the code of P - the state P is in at the moment - whether P has so far visited each possible state The last of these is usually what takes up most of the space. If P is limited to n bits of memory, there are 2^n possible states. Whether a state has been visited is a boolean value, therefore we need only 2^n bits for the entire table. We don't need to store up the bit patterns of these states - which state each bit refers to is evident from its address in H's memory space.

This now makes my hatl.exe capable of 33bit programs :DYou could take this as meaning that the halting problem is solvable within a certain computational class: that in which a finite but arbitrarily large amount of memory must be allocated at the outset. However, we would need to allow the amount of memory to allocate to be a function of the input, which again leads to a problem: when you try to run H on itself, it will need more memory than itself, so the calculation would infinitely recurse.

did I want to suggest that system A could fix its own HP nor that B could fix its HP(you would need system C for that), only that those two systems could sit on the same computer and that A's HP can be done by B. B's halting program only accepts A-size inputs. I never wanted to counter the statement that you need a "stronger" system to do the HP of the "weaker"one, only clarify the meaning of system.So essentially, two computational classes are involved: the one FOR which you are solving the halting problem, and the one IN which you are solving the halting problem. Stewart.

Oct 13 2010

Stewart Gordon wrote:to do it for a setup with n bits of memory, the halt analyser would need 2^n bits.

Depends on how you define memory. If registers and flags of the CPU are not included in your definition of memory, then 2^n bits may not suffice. -manfred

Oct 13 2010

On 13/10/2010 14:17, Manfred_Nowak wrote:Stewart Gordon wrote:to do it for a setup with n bits of memory, the halt analyser would need 2^n bits.

Depends on how you define memory. If registers and flags of the CPU are not included in your definition of memory, then 2^n bits may not suffice.

Maybe I should have kept to using the term "state", which inherently includes all this. Though they could be registers and flags of the interpreter or VM under which the program runs, not necessarily of the CPU per se. Stewart.

Oct 13 2010

Manfred_Nowak <svv1999 hotmail.com> wrote:Stewart Gordon wrote:to do it for a setup with n bits of memory, the halt analyser would need 2^n bits.

Depends on how you define memory. If registers and flags of the CPU are not included in your definition of memory, then 2^n bits may not suffice.

However, those few extra bits won't make all that much of a difference when analyzing real programs. That is, only a few factors of a quintillion. -- Simen

Oct 13 2010