The Halting Problem states, loosely, that there is no algorithm that can 
take an arbitrary computer program and decide [in finite time] whether 
that program will run forever or come to a half after a finite time.

The HP does *not* say that it's impossible to tell whether a program 
halts. It is quite possible to tell that certain programs do in fact 
halt. And it is also quite possible to tell that others are never going 
to halt. The HP says that it is impossible to tell FOR EVERY POSSIBLE 
PROGRAM. Big difference.

To illustrate, consider the following program:

Let A = 0.2499
Let B = 0.01
Let X = 0
Let Y = 0
While (X*X + Y*Y < 4.0)
{
   T = X*X - Y*Y + A
   Y = 2*X*Y + B
   X = T
}
Halt

Does this halt? Or does it run forever?

You know what? If you change the first two lines, you change how long 
the program runs for. For some choices of A and B, the program stops 
instantly. For others, it runs for hours or even days and then stops. 
And for yet others, it runs provably FOREVER.

You might think that some simple mathematical structure describes the 
set of points for which the program does or doesn't stop. You might even 
try to graph this set of points to try to work out its structure. 
Fortunately, you needn't bother. Somebody has already done it for you:

http://tinyurl.com/2ca4o9

Think you can decide whether an arbitrary point on the screen is black 
or white in finite time? If you do, I imagine there are people who would 
be seriously interested to hear from you... ;-)

For each point on the screen, there is essentially a program - the 
program that determines the level set to which that point belongs. To 
repeat what I said above: for many points, it is *easy* to determine 
whether the program will halt. The HP doesn't say otherwise. What it 
says is that you cannot tell for *every* point. And, indeed, looking at 
the image, you can quickly see that whether you run the program directly 
or try to do some tricky geometric stuff, with a boundary this 
complicated, it's going to take a hell of a long time in some cases. 
And, by extension, some cases will unavoidably take an infinite amount 
of time...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> The HP does *not* say that it's impossible to tell whether a program 
> halts. It is quite possible to tell that certain programs do in fact 
> halt. And it is also quite possible to tell that others are never going 
> to halt. The HP says that it is impossible to tell FOR EVERY POSSIBLE 
> PROGRAM. Big difference.

  All complexity class definitions talk about the generic case, not if
there exists at least one case for which the complexity bound does not hold.

  For example, sorting elements using only comparisons between pairs of
elements cannot be done faster than in n*log n steps.
  Of course that means that it's not possible to create an algorithm
which sorts, using comparison only, all possible inputs faster than that.
It doesn't mean there doesn't exist any input which could not be sorted
faster than that using comparisons (an already sorted input is the simplest
case, which can be "sorted" with a linear amount of steps).

  The halting problem belongs to the worst possible complexity class: The
one of unsolvable problems. Of course that doesn't mean there exist no
inputs for which it is solvable. It means that there exist inputs for
which it's not.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   The halting problem belongs to the worst possible complexity class: The
> one of unsolvable problems. Of course that doesn't mean there exist no
> inputs for which it is solvable. It means that there exist inputs for
> which it's not.

That's an interesting way of putting it. I'll have to remember that one...

There seems to be a general misunderstanding that the halting problem 
says it's impossible to determine the output for any program at all. 
Obviously, this is not the case. Similarly, there seems to be a 
misunderstanding that it's "impossible" to solve a 5th order polynomial 
algebraicly. It's not. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> There seems to be a general misunderstanding that the halting problem 
> says it's impossible to determine the output for any program at all. 

  I wouldn't say you constitute what is referred to with "general". ;)

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v7 wrote:
> The Halting Problem states, loosely, that there is no algorithm that can 
> take an arbitrary computer program and decide [in finite time] whether 
> that program will run forever or come to a half after a finite time.

Which has the implication that computers will never be capable of 
handling the process of software engineering without some level of human 
assistance.

Regards,
John

Post a reply to this message

John VanSickle wrote:
> Orchid XP v7 wrote:
>> The Halting Problem states, loosely, that there is no algorithm that 
>> can take an arbitrary computer program and decide [in finite time] 
>> whether that program will run forever or come to a half after a finite 
>> time.
> 
> Which has the implication that computers will never be capable of 
> handling the process of software engineering without some level of human 
> assistance.
> 
You might as well claim that it means that no human can either.

Post a reply to this message

Orchid XP v7 wrote:
> The Halting Problem states, loosely, that there is no algorithm that can 
> take an arbitrary computer program and decide [in finite time] whether 
> that program will run forever or come to a half after a finite time....
> 

After a significant degree of staring at this, I have reached the 
conclusion that the arrow can never be more than halfway there from 
here...  http://en.wikipedia.org/wiki/Arrow_of_time  ...

--Sherry Shaw


-- 
#macro T(E,N)sphere{x,.4rotate z*E*60translate y*N pigment{wrinkles scale
.3}finish{ambient 1}}#end#local I=0;#while(I<5)T(I,1)T(1-I,-1)#local I=I+
1;#end camera{location-5*z}plane{z,37 pigment{granite color_map{[.7rgb 0]
[1rgb 1]}}finish{ambient 2}}//                                   TenMoons

Post a reply to this message

John VanSickle <evi### [at] hotmailcom> wrote:
> Which has the implication that computers will never be capable of 
> handling the process of software engineering without some level of human 
> assistance.

  Humans are bound to the same limitations as computers. If it has been
proven that a certain problem is not solvable, a human cannot solve it
either.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> John VanSickle <evi### [at] hotmailcom> wrote:
>> Which has the implication that computers will never be capable of 
>> handling the process of software engineering without some level of human 
>> assistance.
> 
>   Humans are bound to the same limitations as computers. If it has been
> proven that a certain problem is not solvable, a human cannot solve it
> either.
> 
See, sometimes we do agree ;)

Post a reply to this message

Warp wrote:

>   Humans are bound to the same limitations as computers. If it has been
> proven that a certain problem is not solvable, a human cannot solve it
> either.

Curiosly, they just happen to be having this exact debate on one of the 
Haskell mailing lists right now. (Evidently some people actually believe 
that the human mind is capable of deductions that are beyond 
Turing-completeness. Naturally, they offer no basis for this belief 
beyond the fact that computers don't program themselves yet...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message