|
![](/i/fill.gif) |
Ah yes, it is impossible to write a computer program that can analyse
any possible computer program and tell you whether it halts in a finite
number of steps.
After reading about Cantor's diagonal argument, the cardinality of the
continuum, Turing degrees, and other mind-blowing stuff, it seems that
the *reason* the Halting Problem is undecidable boils down to this:
If there was a Magic() subroutine that could take the object code to
your whole program and tell you whether it halts or not, then you could
write a BlackMagic() subroutine that calls Magic(BlackMagic()) and then
purposely does the opposite of whatever Magic() claims that it's going
to do. Hence, it is impossible for Magic() to yield the correct answer,
since BlackMagic() will do the opposite of whatever Magic() claims it
will do.
Interestingly, even if you build some kind of hyper-computer that can
solve the Halting Problem, then by the argument above you could define a
new Hyper-Halting Problem which the hyper-computer would be just as
powerless to solve.
Looking the other way, the argument above doesn't work if the program to
be analysed isn't allowed to call Magic(), or perhaps one of the
operations used within Magic(). Which seems to just restate the fact
that a system can only prove results about systems weaker than itself.
Oddly enough:
http://mathworld.wolfram.com/HaltingProblem.html
"The halting problem is solvable for machines with less than four states."
That doesn't quite sound right...
The Halting Problem cannot be solved. You cannot write a program which
can decide for *every possible program*. But can you write one for "the
kind of programs that human beings tend to write"?
Well, first of all, good luck finding a rigorous definition for "the
kind of programs that human beings tend to write". But, assuming you
find one, the argument above still seems to apply. In other words, if it
*is* somehow possible to write a program that can determine whether
hand-written programs halt, the solution program cannot be hand-written. (!)
Another puzzling thing: Deciding whether a program halts within, say,
1000 steps *is* trivially solvable. Just run the program for (up to)
1000 steps, and see if it halts.
It's quite obvious that that ought to work. However, it looks like the
argument above should still apply, making it impossible to solve this
problem.
So what happens if you implement Magic() this way? Does BlackMagic()
halt or not halt? It seems that BlackMagic() would immediately call
Magic(), which would immediately begin simulating BlackMagic(), which
would immediately call Magic(), which would start simulating
BlackMagic()... Eventually, at some point, the top-level Magic() would
give up on its simulation and report back to the top-level BlackMagic()
that BlackMagic() takes more than 1000 steps to execute. Whereupon...
...Magic() has already used up thousands of cycles, and therefore
BlackMagic() can't be contrary and halt in less than 1000 cycles to
invalidate the analysis. Ah, trixy!
So it seems that the fallacy of solving the Halting Problem is in
Magic() being able to predict the outcome of an infinite number of
cycles of work with some finite number of cycles of processing.
Interesting...
That suggests another interesting question: Can you write a program that
takes any possible terminating program, and yields the same result in
strictly fewer steps? (E.g., if program P yields a result in K steps,
program Q given program P as input yields the same result in only K-1
steps.)
Unlike the Halting Problem, nobody would seriously expect the answer to
be no. Which is interesting, because when you think about it, they're
very similar programs really.
If Magic(P) computes the same thing as P but takes exactly 1 fewer
steps, then Magic(Magic(P)) computes the same thing in 2 fewer steps.
And by induction, by applying Magic() enough times, any result can be
computed in zero steps, which is impossible. Hence, Magic() does not
exist (or at least, doesn't work properly).
Here we're talking about *computation* compression, which is not unlike
the *data* compression case. If a compression algorithm could always
compress data by at least 1 bit, you could compress anything into zero
bits. And, conversely, decompress zero bits into anything. The latter is
obviously impossible.
The way the theorem is usually phrased is that "K bits can represent 2^K
possibilities, but K-1 bits can only decompress into 2^(K-1)
possibilities, which is *half* as many". I suppose you could relate the
number of cycles that a program runs for to the number of possible
outputs it can generate and prove it that way...
I note with some interest that if it's impossible for a program to not
halt, then the Halting Problem becomes [trivially] solvable. That's
cute. But why is it true? Because BlackMagic() tries to not halt if
Magic() says it should halt. It non-termination is impossible, then
BlackMagic() cannot have its evil way.
In fact, it seems that Magic() can function correctly so long as you
can't implement BlackMagic(), or something equivalent to it. So if you
want to know how to make the Halting Problem tractable, maybe you just
need to look at what components are required to implement BlackMagic()
[assuming that Magic() already exists].
For example, it appears as if it ought to be possible to implement
Magic() as a partial function that is defined only for programs that do
not call Magic(), nor contain an instruction sequence isomorphic to it.
In reality, I guess that might be quite a big limitation. For example,
there is Rule 30. This cellular automaton can be computed by the logic
function Y' = X xor (Y or Z). So I imagine with just a few bitwise (or
even integer arithmetic) instructions, you could implement Rule 30. And
it's known to be Turing-complete. Oh dears...
Post a reply to this message
|
![](/i/fill.gif) |