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 [lcamtufat_private] [security] [http://lcamtuf.coredump.cx] <=-=> bash$ :(){ :|:&};: =-=> Did you know that clones never use mirrors? <=-= http://lcamtuf.coredump.cx/photo/
This archive was generated by hypermail 2b30 : Thu Mar 28 2002 - 08:59:06 PST