RE: New Binary Bruteforcing Method Discovered

[Michal Zalewski <lcamtuf () coredump cx>]

On Thu, 28 Mar 2002, Michael Wojcik 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.

What makes you think I said the opposite? I was trying to explain why the
halting problem is affecting our ability to predict the behavior of
"finite tape" machines in most real-life scenarios. Being able to answer
(in finite time, which is what I mentioned several times) the question
about halting or not for "infinite tape" TM would have very interesting
implications, among others, the ability to "detect all exploitable
vulnerabilities" as soon as we define what the vulnerability is, but I am
not trying to imply that there can be an answer to the halting problem
other than "it is impossible". I am aware that is can be trivially proven.

My initial question was a pure irony. Then, I was questioned by somebody
who said that the halting problem does not really affect finite machines
(real computers). My answer to that was that yes, it does, in a
hypotetical world where it does not exist (read: you can answer the
halting question), it would let you answer a question about a behavior of
any finite machine in much more feasible manner than we can right now
(which means we practically cannot in most interesting cases, such as
operating systems). But quite unfortunately, our world is different and
that is why I asked 'Did you solve this nasty halting problem?' and
followed it with something like ';-)'.

-- 
_____________________________________________________
Michal Zalewski [lcamtuf () bos bindview com] [security]
[http://lcamtuf.coredump.cx] <=-=> bash$ :(){ :|:&};:
=-=> Did you know that clones never use mirrors? <=-=
          http://lcamtuf.coredump.cx/photo/