Re: HALTING DISPROOF

From: Michael N. Christoff (mchristoff_at_sympatico.caREMOVETHIS)
Date: 05/17/04

  • Next message: Michael N. Christoff: "Re: HALTING DISPROOF" 
    Date: Mon, 17 May 2004 07:34:57 -0400

    "|-|erc" <gotchy@beauty.com> wrote in message
    news:djzpc.40652$TT.30082@news-server.bigpond.net.au...
    > Assume a simple infinite set of all TMs. Alternatively assume a simple
    UTM that
    > covers all TMs represented as naturals.
    >
    > Then, all computing power is represented by the set N.
    > The problem (and this is just a problem for you not me) is that some of
    the
    > TMs don't halt.
    >
    > Now assume infinite processing on the entire set of TMs, what do you have?
    >
    > You have a subset of N that are all demonstrably halting functions. This
    set I have always
    > thought is as powerful in computation as all N. Now everyone is arguing
    non-halting functions
    > add some power to functions but we can forget that for now that's just a
    copout.
    >

    The problem is that the set of demonstrably halting functions DH is a proper
    subset of the set of of ALL halting functions H.

    ie: DH is a subset of H, but H is not a subset of DH.

    > Now, to disprove a function halt exists, you have to be able to call
    functions and embed
    > them within other functions. This is not a paradigm of TMs.
    >
    > HALTING PROOF
    > 1 Assume a TM1 exists that inputs Naturals n and p, and outputs 1 iff
    UTM(n, p) halts.
    > 2 Assume another TM2 calls TM1(n, n) and goes into an infinite loop iff
    UTM(n, n) halts.
    > If TM2(n) halts, UTM(n, n) didn't halt.
    > If TM2(n) didn't halt, then UTM(n, n) halted.
    > Therefore UTM(n, n) can never equal TM2(n),
    > !En, UTM(n) = TM2,
    > the assumed function TM2 is therefore not compuable.
    >

    The first thing I notice is that

    > If TM2(n) halts, UTM(n, n) didn't halt.

    is impossible, since if UTM(n,n) didn't halt, then TM1 never halts and hence
    TM2 never halts either. So in fact, TM2 never halts (on any input). This
    means the TM2 is equivalent to the following TM:

    TM3(n)
        loop forever (ignoring the input)

    and any UTM can obviously simulate this TM.

    l8r, Mike N. Christoff

  • Next message: Michael N. Christoff: "Re: HALTING DISPROOF"

    Relevant Pages
    Loading