> From: mixterat_private [mailto:mixterat_private] > 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
This archive was generated by hypermail 2b30 : Thu Mar 28 2002 - 08:23:16 PST