Re: New Binary Bruteforcing Method Discovered

[Blue Boar <BlueBoar () thievco com>]

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