RE: New Binary Bruteforcing Method Discovered

From: Michael Wojcik (Michael.Wojcik@microfocus.com)
Date: 03/28/02 

From: Michael Wojcik <Michael.Wojcik@microfocus.com>
To: vuln-dev@securityfocus.com
Date: Thu, 28 Mar 2002 06:56:51 -0800

> 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

Relevant Pages

  • Re: Halting tester proof for software engineers without self-reference
    ... unsolvable then an all-knowing mind can not solve it. ... The proof does not say that the Halting problem is unsolvable. ... that such an all-knowing mind is not emulatable by a Turing machine, ... Bob will wait for someone to ask Alice the infallible Turing machine, "Will Bob halt on input XYZ?" ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (sci.logic)
  • Re: Halting tester proof for software engineers without self-reference
    ... unsolvable then an all-knowing mind can not solve it. ... The proof does not say that the Halting problem is unsolvable. ... that such an all-knowing mind is not emulatable by a Turing machine, ... Bob will wait for someone to ask Alice the infallible Turing machine, "Will Bob halt on input XYZ?" ...
    (comp.theory)
  • Re: Exploiting limitations of Turing machines in Turing tests?
    ... correctly answer _any_ halting problem question. ... You were proposing that there exists some finite set of special Turing ... able to successfully answer _all_ halting problem questions. ... It's a description of some Turing Machine, and some input, with the simple ...
    (comp.ai.philosophy)