Re: Cardinality of Set of Computable Numbers?

From: George Greene (greeneg_at_cs.unc.edu)
Date: 12/30/03 

Date: 29 Dec 2003 15:08:02 -0800

"Russell Easterly" <logiclab@comcast.net> wrote in message news:<Bu-dnYP-tIz1JHOiRVn-sA@comcast.com>...
> "Pento" <robby.goetschalckx@student.kuleuven.ac.be.NOSPAM> wrote in message
> news:Xns945F37E9E9C54robbygoetschalckxstu@134.58.127.12...
> > "Russell Easterly" <logiclab@comcast.net> wrote in
> > news:q8CdnfPGJ8E4knOiRVn-tw@comcast.com:
>
> > >
> > > I give a constructive method of creating a RM computable number, x,
> > > that is not in S. How can my method fail to produce x?

You have yet to say What KIND of numbers RM numbers CAN OR CAN'T be.
Are they natural? Rational? Real? Complex? Supernatural? Infinitesimal?
IT MATTERS. ANSWER the question!

> >
> > Because every x would be of the form (0)11..1, and because of the
> > definition of S, any such RM number is contained in S.
>
> The definition of S leads to contradiction.

No, it doesn't.

> S can not contain every natural number.

It can and it does.
YOU defined it. Do you have any idea how
STUPID this makes you look, defining a set and then
saying that it can't contain things it obviously contains?

>
> > > You assume that every string that corresponds to a finite number is in
> > > S.

No, we don't assume it, we just NOTICE it.
You defined S as the class of all outputs of RMs that printed
some natural number of 1s and then stopped.

> This is not true if my proof is correct.

Ergo, your "proof" is not one.

> > That was how S was defined : it contains all the strings of the form
> > (0)11..1 (this can be considered as all unary representations of natural
> > numbers).

YOU defined S that way. So S contains all natural numbers.

> I show that there exists an RM computable number of the form (0)11...1
> that is not in set S.

No, you don't.

> I can even show how this number can be constructed
> by a Turing machine.

No, you can't.
 
> RM's are a subset of TMs.

No, they're not. For one thing, you alleged that they never halted.
Are you going to retract that?

> Any RM can be emulated by a universal Turing machine (UTM).
> We are only concerned with the subset of RM's that output an initial,
> finite and contiguous string of 1's followed by an infinite string of 0's.

Since RM output tapes were supposed to START OUT as all 0's, can't the
the RM just HALT after it gets through printing all its 1's?

> The UTM can generate the output tape for each of these RM's.

And put it where, exactly? TM's, by default, only have ONE output tape.

> These tapes are then read by a second TM I will call a Comparator (CTM).

No, they aren't. There are an infinite number of these tapes and the CTM
never finishes reading them all.
 
> The CTM compares each input tape with the CTM's output tape.

The CTM does NOT HAVE an output tape, other than its input tape.
That's just how TMs ARE DEFINED.

Relevant Pages