Re: New Binary Bruteforcing Method Discovered

From: Blue Boar (BlueBoar@thievco.com)
Date: 03/28/02 

Date: Thu, 28 Mar 2002 08:58:19 -0800
From: Blue Boar <BlueBoar@thievco.com>
To: Michael Wojcik <Michael.Wojcik@microfocus.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

Relevant Pages

  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (sci.logic)
  • Re: Exploiting limitations of Turing machines in Turing tests?
    ... correctly answer _any_ halting problem question. ... You were proposing that there exists some finite set of special Turing ... able to successfully answer _all_ halting problem questions. ... It's a description of some Turing Machine, and some input, with the simple ...
    (comp.ai.philosophy)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (sci.logic)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (comp.theory)