Re: functions that halt

From: |-|erc (contactvia_at_wwwadamskingdom.com)
Date: 04/16/04

  • Next message: |-|erc: "Re: functions that halt" 
    Date: Fri, 16 Apr 2004 08:42:10 +1000

     \ oo
       \____|\mn
        / /_/ /\ \_\ - Herc, The Unrecognised Truman
      / K-9/ \/_/ - Join www.chatty.net -
    /____/_____\ - Nanotechnology is gonna be HUGE... (RMF)
    --------------

    "Michael Mendelsohn" <keine.Werbung.1300@msgid.michael.mendelsohn.de> wrote
    > > > Does it disprove Barbs diagnonalistion attack on a theory of
    > > > guaranteed halting functions being equivalent in power to the
    > > > class of TMs?
    > >
    > > Yes, as the diagonalization function cannot be placed in a TM.
    >
    > Oh, but it can.
    >
    > The point of the guaranteed halting functions (GHF) is that you *can*
    > enumerate them, i.e. you can write a function that gives you the k'th
    > GHF.
    > If you grant a mechanism that allows to to actually call such a
    > function, or, what amounts to the same thing, "emulate" it (i.e. parse
    > it and see what it does), you can write the diagonalisation function
    > (DF).
    >
    > The only problem is that you can't guarantee the DF to halt if it is a
    > GHF, because it then calls itself (or a simile of itself) in an infinite
    > recursion.
    > In other words, there is no contradiction if the diagonalisation
    > function is not a GHF.
    >

    Right! If a function is proven to halt does that make it a member of GHF?
    Guarantee can be interpreted either way, guarantees have to be 'given'.

    PROOF that guarantees have to be given.

    Assume any program that is proven to halt is in GHF. (1)
    Assume the standard F(i,j) being the jth output of the ith GHF.
    Let G(j) = F(j,j) mod 2 + 1
    Since F halts by inspection G halts (2)
    (1),(2) -> G is in GHF.

    But G is not any F(i), CONTRADICTION.
    Therefore not all programs that halt are in GHF.

    A systematic Guarantee could include not granting any mechanism to
    call a function. This would ensure any encapsulation of G into a form
    of Godel numbering would be impossible.

    Herc

  • Next message: |-|erc: "Re: functions that halt"