Michael Wojcik wrote: > > 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. Just to be pedantic (because I was a CS major), the proof shows that you can't solve the halting problem with a UTM *for all programs*. You could, for example, design code to determine if hello world halts. BB
This archive was generated by hypermail 2b30 : Thu Mar 28 2002 - 09:56:39 PST