Re: Cardinality of Set of Computable Numbers?

From: George Greene (greeneg_at_greeneg-cs.cs.unc.edu)
Date: 12/29/03 

Date: 29 Dec 2003 17:13:04 -0500

comp.theory and sci.math need to come off the list of newsgroups
for this thread. Those groups surely have more important things
to discuss.

 : "Russell Easterly" <logiclab@comcast.net> writes:
 :
 : Consider all TM's that write an initial, finite and contiguous strings of
 : 1's
 : and then halt.

OK. There is one of these TMs for every natnum.

 : Let S be the set of all output tapes from these TM's.

That's basically the set of all natural numbers.

 : Define another TM I call a comparator (CTM).
 : CTM compares the input tape to its output tape.

CTM *DOES* *NOT* *HAVE* an output tape.
CTM is a TM. In general, TMs DO NOT HAVE output tapes.
TMs have ONE tape. They use it for input.
They also write on it, but that does not make it an output tape.
It is at best an input/output tape.

 : If the input tape has more 1's,

This is ridiculous. The input tape IS the output tape, if CTM
is a TM. It can NEVER have a DIFFERENT number of 1's from itself.

 : the CTM rewinds to the beginning of its output tape, copies the input tape,
 : and then writes an additional 1 to the end of the output.

That is not how TMs work. What actually happens is that the TM reads
its input tape until it gets to the last 1, and then writes another 1
at the end, and then halts.

 : We let CTM read all the tapes in S.

No, we don't, because S has an infinite number of tapes, so CTM
(if it really is a TM, which, as you have defined it, IT ISN'T,
because it has an output tape) will never finish reading all
these tapes.

 : What is on the output tape of CTS?

That's a typo; CTS does not exist; do you mean CTM?

 : The output of CTM must have a finite number of 1's.

Right.

 : Every tape read by CTM was finite in length.

Right.

 : The output of CTM has exactly one more 1 than
 : some input tape in S.

Wrong.
S has infinitely many input tapes and there is no upper bound on
how long they are.

 : S can not contain every possible string that
 : represents a natural number.

As you defined it, it does indeed contain exactly that;
it represents the natnums in unary. 

-- 
 ---
  "It's difficult ... you need to be united to have any 
   strength, but internal issues have to  be addressed."
 --- E. Ray Lewis, on  liberalism in America

Relevant Pages

  • Re: Cardinality of Set of Computable Numbers?
    ... > The UTM can generate the output tape for each of these RM's. ... > The CTM compares each input tape with the CTM's output tape. ... > The CTM output tape contains the representation of the successor ...
    (comp.theory)
  • Re: Cardinality of Set of Computable Numbers?
    ... CTM compares the input tape to its output tape. ...
    (comp.theory)
  • Re: Cardinality of Set of Computable Numbers?
    ... finite and contiguous string of 1's followed by an infinite string of 0's. ... The UTM can generate the output tape for each of these RM's. ... These tapes are then read by a second TM I will call a Comparator (CTM). ...
    (comp.theory)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... > There does not a exist Turing Machine H, such that for all M in TM ... > the tape of H. ... write and om is the motion for the output tape. ... The "halting problem" takes a machine M and input x and decides ...
    (comp.theory)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... > There does not a exist Turing Machine H, such that for all M in TM ... > the tape of H. ... write and om is the motion for the output tape. ... The "halting problem" takes a machine M and input x and decides ...
    (sci.logic)