www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [Theory] Halting problem

reply %u <e ee.com> writes:
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
next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
%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
parent reply %u <e ee.com> writes:
== 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
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
"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
next sibling parent Justin Johansson <no spam.com> writes:
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
prev sibling parent reply %u <e ee.com> writes:
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
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
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
parent reply %u <e ee.com> writes:
== Quote from Norbert Nemec (Norbert Nemec-online.de)'s article
 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.

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
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
On 10/10/10 19:36, %u wrote:
 == Quote from Norbert Nemec (Norbert Nemec-online.de)'s article
 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.

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
parent reply %u <e ee.com> writes:
== Quote from Norbert Nemec (Norbert Nemec-online.de)'s article
 On 10/10/10 19:36, %u wrote:
 == Quote from Norbert Nemec (Norbert Nemec-online.de)'s article
 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.


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
parent Norbert Nemec <Norbert Nemec-online.de> writes:
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
prev sibling next sibling parent reply BCS <none anon.com> writes:
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
parent %u <e ee.com> writes:
== Quote from BCS (none anon.com)'s article
 Hello %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
prev sibling next sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
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
prev sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
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
next sibling parent reply %u <e ee.com> writes:
== Quote from Stewart Gordon (smjg_1998 yahoo.com)'s article
 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.

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
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
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
parent %u <e ee.com> writes:
== Quote from Stewart Gordon (smjg_1998 yahoo.com)'s article
 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

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 :D
 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.

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
prev sibling next sibling parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
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
parent Stewart Gordon <smjg_1998 yahoo.com> writes:
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
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
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