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

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]