RE: New Binary Bruteforcing Method Discovered

[Michael Wojcik <Michael.Wojcik () microfocus com>]

> From: mixter () 2xs co il [mailto:mixter () 2xs co il]
> Sent: Wednesday, March 27, 2002 4:06 PM
>
> On Wed, 27 Mar 2002, Michal Zalewski wrote:
>
> > Knowing the way to solve the halting problem for infinite 
> > Turing machines in finite time would very likely enable us to
> > perform this analysis for finite machines in no time (and have
> > dramatic implications not only for computer security).

The Halting Problem isn't an unsolved conjecture (like P!=NP), it's a proven
theorem.  Turing's proof shows that no Universal Turing Machine can solve
the HP (in finite time, which is the whole point of the HP).  By extension,
no machine less powerful than a UTM can solve it.  That includes digital
computers, which are just resource-constrained Turing Machines.  There's no
"knowing the way to solve" it to be had.

Quantum "computers" (which aren't precisely digital) *might* be a different
story, but I've never seen a QC algorithm that gets around Turing's proof.
It would have to be a QC algorithm that for some reason can't be simulated
on a digital computer, which seems very unlikely to me, but I'm not a QC
expert by any means.  (Ditto any other sort of non-digital computing device
- for it to be able to avoid Turing's proof, it has to be more powerful than
a UTM, and hence couldn't be simulated by a UTM.)

The proof's very simple - it's just a matter of self-referential proof by
negation, where you assume a machine that solves the HP exists, then you
tinker with it a bit and feed it to itself.  It's similar to Godel's
Incompleteness proof.  Any decent intro to computer science covers it.

> Would you say that human beings can theoretically solve this 
> problem

If the human mind is a Turing Machine, then no.  That the human mind is a
Turing Machine is an unproven conjecture.  Some people (Roger Penrose, for
example) believe it to be false.

> If so, do you think AI could eventually solve the problem...?

No AI algorithm executing on a digital computer can solve the Halting
Problem.  Ever.  End of story.

Now, the HP is a strong problem: solving it means being able to take *any*
program and tell whether it will eventually halt.  Turing's proof shows that
there's a class of programs which can never be analyzed for "haltingness" by
a UTM (and since it's possible to turn any binary program characteristic
into a halt-or-loop situation, that covers any other aspect of program
analysis), but that doesn't mean that some UTM algorithm couldn't be devised
that analyzed "most" of the "interesting" programs that would likely be fed
to it.  What the HP proof does - as Michal originally pointed out - is
strike down absolute claims like "this analysis program can find any bug".

Michael Wojcik
Principal Software Systems Developer, Micro Focus
Department of English, Miami University