Re: PROOF that numbers are countable

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 05/16/04 

Date: Sun, 16 May 2004 12:53:01 -0600

On Sun, 16 May 2004, The Ghost In The Machine wrote:

> 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: [*]
>
> 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

  Based on g2(m,0)=1, and your first condition above, it would seem that
g2(m,1) = 1, then g2(m,2) = 1, and g2(m,k) = 1 for all k. I'm not sure
exactly what you were trying do with this function, but the other two
cases (which never occur) looks like you're trying to dscribe the Collatz
conjecture.

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

  Right... it does one or the other, but which one it is we do not know.
This is pretty irrelevant to the discussion, though.

> 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.

  Provided the formalism is sufficiently powerful. So why don't we just
stick with turing machines or a standard programming language? Anything
computable in one 'formalism' will also be computable in the other
'formalism,' but perhaps with a slow-down or a speed-up, but that does not
affect the notion of computability.

> 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.

  Being recursively enumberable does not conflict with the fact that it is
undecidable. Consult an introductory book on computability theory.

  He described the method to generate a list, and it is elegant and it can
be found in a standard book (the method running the first program for 1
step, running the first two programs for 1 more step each, running the
first three programs for 1 more step each, and so on.) Herc's list does
NOT filter out non-halting algorithms, since it never finds a non-halting
algorithm. It essentially runs all programs and once some problem halts,
it will be output to the list. Another way to characterize a recursively
enumerable set is to say that the set has the property that, given an
element to test membership into the set (i.e. given a program to test
whether it is a halting one) there exists an algorithm to say "yes" for
any input that should be answered "yes" while having no requirement to
report "no" in the case that the word does not belong in the set.
Obviously, such an algorithm exists, and that is to run the program and
wait for it to halt. If it ever halts in finite time, we report 'yes' in
finite time. If the program never halts, then our algorithm will be
waiting forever to detect it's termination, and since it will never come,
it will never report 'no' and will continue waiting in hopes of eventually
reporting 'yes.'

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

  A whole new issue altogether. You can form turing machine-like models
with an oracle that solves the halting problem if you like. It's not new,
though.

J

Relevant Pages

  • Re: PROOF that numbers are countable
    ... >> Is fa function (as opposed to merely an algorithm that may or ... >> AIUI one formalism is equivalent to another. ... Consult an introductory book on computability theory. ... It essentially runs all programs and once some problem halts, ...
    (comp.theory)
  • Re: Congruence based factoring algorithm
    ... algorithm will run faster with as small a p as possible; ... report that T is prime ... Report as a factorization of T ... and the GCD test becomes an evenness test. ...
    (comp.theory)
  • Re: Problem demonstrating that the set of binary strings is uncountable.
    ... I doubt that the concept of recursive enumerability is part of CS-101. ... The Cantor proof still makes no use of computability. ... I have been claiming that it doesn't. ... > I keep trying to bring you to focus on the algorithm. ...
    (sci.math)
  • Re: Is a general purpose mechanism possible?
    ... AIXI based on Solomonoff's Algorithmic Probability is not computable ... computability means merely to assume that there exist laws governing ... will quarantee an algorithm which exploits every possible symmetry, ... invariant and pattern in the data. ...
    (comp.ai.philosophy)
  • Re: Uncountable doesnt exist
    ... Suppose that the algorithm is ... > |> theorem says that either S contains all computable reals, ... > |computability. ... > infinite classes of problems. ...
    (sci.math)