Re: PROOF that numbers are countable

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 05/16/04

  • Next message: Klaus Glashoff: "Re: THeoremProver.com is ONLINE!" 
    Date: Sun, 16 May 2004 04:00:08 GMT

    In sci.logic, Jim Nastos
    <nastos@cs.ualberta.ca>
     wrote
    on Sat, 15 May 2004 11:36:08 -0600
    <Pine.LNX.4.44.0405151123430.12378-100000@eva117.cs.ualberta.ca>:
    > On Sat, 15 May 2004, The Ghost In The Machine wrote:
    >
    >> In sci.logic, |-|erc
    >> <gotchy@beauty.com>
    >> wrote
    >
    >> > My proof is finished, you reply nonsense all over it. The OP was : is a set of
    >> > halting functions possible, then it would evade the halting proof as the infinite
    >> > loop in that proof would be dissalowed. The answer so far is yes, unless
    >> > you have some proof otherwise. The only rebuttal was diagonalisation over the
    >> > set, which is invalid considering diagonalisation will only work on a function
    >> > calling paradigm of algorithms, not more elementary systems.
    >
    > <snip>
    >
    >> Do you have a webpage describing your halting proof in finished form?
    >> Also, does your proof allow construction of a halting algorithm,
    >> given code in a certain form?
    >>
    >> Such a construct would be a boon to mankind, especially if given to
    >> a commercial concern such as Sun, IBM, or Microsoft; the vendor would
    >> develop a checking system around it which could be used by IT
    >> corporations (or at least QA divisions within them) to determine
    >> whether a function can halt, given certain input.
    >
    > Herc's method of producing a list of all halting programs shows that the
    > set of halting programs is *recursively enumerable* (this means
    > "semi-decidable" or "semi-computable.") This does NOT contradict the fact
    > that the halting problem is undecidle.

    Interesting, though I for one would suspect that such a recursively
    enumerable list would in fact be a proper subset. Consider,
    for instance, the functions that map W x W -> W: [*]

    f2(m,0) = 0
    g2(m,0) = 1

    g2(m,n+1) = g2(m,n) if g2(m,n) = 1
              = g2(m,n)/2 if g2(m,n) is even
              = 3 * g2(m,n) + 1 if g2(m,n) is odd and != 1

    f2(m,n+1) = f2(m,n) if g2(m,n) = 1
              = f2(m,n)+1 if g2(m,n) != 1

    It is obvious that f2() and g2() are primitive recursive -- at
    least, such is my understanding. Now generate the function: W -> W
    that could be described

    f(m) = "f2(m,+oo)"

    or perhaps

    f(m) = min n such that f2(m,n+1) = f2(m,n)

    Is f(m) a function (as opposed to merely an algorithm that may or
    may not halt)? I for one don't know.

    There's a name for this conjecture but I can't say I remember it offhand.
    g2() implements the steps through the conjecture; f2() counts them.

    > In terms of lists, the difference between a recursively enumberable
    > (i.e. semi-decidable) set and a recusive set (i.e. computable/decidable)
    > is that a set can be listed out in some canonical ordering (say,
    > lexicographic order) IF AND ONLY IF the set is computable. If it is
    > semi-decidable, then one could output the elements of that set in some
    > order in which it would be impossible to find out where a certain element
    > should appear in that list.
    >
    > It's no boon to mankind, nor is this is a huge breakthrough in anything.
    > This is all covered in a first course in computability theory and the
    > listing result that Herc uses is the standard way to show that a set is
    > recursively enumerable directly from its definition.

    You might have noticed the bulge in my cheek as I wrote the above. :-)

    It's quite obvious the halting problem is undecidable
    within a certain formalism. (The one I happen to like is an
    idealized assembly language -- not an original idea, BTW;
    consult the works of Ronald V. Book, if I'm remembering the
    name correctly. He used to teach complexity theory at my
    alma mater -- and I don't know if he originated the idea,
    either.)

    AIUI one formalism is equivalent to another. Not sure where
    the proof of that is; I'd have to look.

    Besides, what is a computer anyway? It's a giant Turing
    machine with no tape. (Well, one could mimic a tape,
    of course, by feeding it a DAT, or an infinite set of
    blank CD's or DVD's to scribble on. There are admittedly
    a number of technical issues here.)

    >
    > Now some might say "but what about the diagonal proof?" The diagonal
    > proof relies on some precise ordering of the elements of a set, i.e. it
    > requires a first element, a second element, a third element, etc. Herc's
    > generation of the list can not guarantee what element will appear at the
    > i(th) position.
    >
    > That is all there is to it.

    There's probably no elegant method to even generate the list, as
    the halting problem is undecidable anyway; Herc's list filters
    out the non-halting algorithms.

    To me that's either a form of begging the question or putting
    an oracle into a computability/complexity problem.

    >
    > J
    >

    [*] W = the set of whole numbers = {0, 1, 2, 3, ...}. I'm not sure if
        this is standard or not. 

    -- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.
  • Next message: Klaus Glashoff: "Re: THeoremProver.com is ONLINE!"

    Relevant Pages