digitalmars.D  [Theory] Halting problem
 %u (12/12) Oct 09 2010 Just to be clear about this, the halting problem is only unsolvable for ...
 Simen kjaeraas (5/20) Oct 09 2010 Of course. However, for nontrivial programs it is hard enough that we
 %u (7/16) Oct 09 2010 This may be, but too often I see the theoretical(truly impossible) probl...
 Norbert Nemec (7/24) Oct 10 2010 "Impossible to solve" is often used synonymous to "exponentially hard to...
 Justin Johansson (4/10) Oct 10 2010 That's a fair observation.
 %u (9/39) Oct 10 2010 I am not sure where exactly the line lies where people tend to use impos...
 Norbert Nemec (11/19) Oct 10 2010 I think, the essence here is the "limited memory" issue. A turing
 %u (11/31) Oct 10 2010 I don't know people in language design, but I suspect they know their st...
 Norbert Nemec (5/20) Oct 10 2010 I know that situation very well: having the big Ahaeffect after years
 %u (8/28) Oct 10 2010 No no no! :D
 Norbert Nemec (9/16) Oct 12 2010 Sorry, my wording was extremely poorly chosen.
 BCS (5/8) Oct 12 2010 More correctly, the halting problem for machine X is unsolvable by machi...
 %u (6/12) Oct 12 2010 I was looking for a way out by making machine X allocate only 32b per pr...

Stewart Gordon
(17/19)
Oct 12 2010
 Stewart Gordon (7/14) Oct 12 2010 I get it now under the assumption that these aren't stepbystep
 %u (5/20) Oct 12 2010 Yep, it needs to run in a minimal 2^n larger limited memory system (n2^n...
 Stewart Gordon (26/29) Oct 13 2010 n2^n? Are you sure?
 %u (10/39) Oct 13 2010 You are totally right, I took the "store the state" a bit too literal.
 Manfred_Nowak (4/6) Oct 13 2010 Depends on how you define memory. If registers and flags of the CPU are ...
 Simen kjaeraas (5/11) Oct 13 2010 However, those few extra bits won't make all that much of a difference
 Stewart Gordon (6/11) Oct 13 2010 Maybe I should have kept to using the term "state", which inherently
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 limitedmemory 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 limitedmemory 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 nontrivial 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: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?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 nontrivial programs it is hard enough that we may consider it impossible.
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 prefactor, 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: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?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 nontrivial programs it is hard enough that we may consider it impossible.
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 prefactor, 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 Nemeconline.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 prefactor, 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: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?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 nontrivial programs it is hard enough that we may consider it impossible.
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 Nemeconline.de)'s articleOn 10/10/10 17:06, %u wrote:This is correct.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 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.I don't know people in language design, but I suspect they know their stuff and I 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 Nemeconline.de)'s articleBasically: because 1GB=infinity for all purposes of logical reasoning.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.I don't know people in language design, but I suspect they know their stuff and I 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.I know that situation very well: having the big Ahaeffect 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 Nemeconline.de)'s articleOn 10/10/10 19:36, %u wrote:No no no! :D 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! ..== Quote from Norbert Nemec (Norbert Nemeconline.de)'s articleBasically: because 1GB=infinity for all purposes of logical reasoning.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.I don't know people in language design, but I suspect they know their stuff and I 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.I know that situation very well: having the big Ahaeffect 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
On 10/10/2010 09:16 PM, %u wrote: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".Basically: because 1GB=infinity for all purposes of logical reasoning.No no no! :D 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!
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,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.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).
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.<snip> 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 limitedmemory 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 stepbystep instructions. But can this algorithm run within this limitedmemory 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>Sorry :(In the more general limitedmemory 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 stepbystep instructions.But can this algorithm run within this limitedmemory 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 :Dn2^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>You are totally right, I took the "store the state" a bit too literal. This now makes my hatl.exe capable of 33bit programs :DYep, 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 :Dn2^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.The idea was that we had two systems; A(max n bits) and B(min 2^n bits) but never 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 Asize 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.Exactly ;)
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
Manfred_Nowak <svv1999 hotmail.com> wrote:Stewart Gordon wrote: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.  Simento 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.
Oct 13 2010
On 13/10/2010 14:17, Manfred_Nowak wrote:Stewart Gordon wrote: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.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.
Oct 13 2010