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.


 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.


This is correct.


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


 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.


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.


 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.


 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!
..


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


 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!


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.


 More correctly, the halting problem for machine X is unsolvable by machine
 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.


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


 I get it now under the assumption that these aren't step-by-step
 instructions.


Sorry :(


 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


 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 are totally right, I took the "store the state" a bit too literal.
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.


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


Exactly ;)
Oct 13 2010
prev 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
next 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
prev sibling 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