Re: Cardinality of Set of Computable Numbers?

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 12/29/03 

Date: Sun, 28 Dec 2003 22:58:10 -0500 (EST)

On Sun, 28 Dec 2003, Russell Easterly wrote:
>
> "Barb Knox" <see@sig.below> wrote...
  [ Obviously, every natural number N is computable by an N-state FSM. ]
> > So in what sense isn't every natural number computable?
>
> Consider all TM's that write an initial, finite and contiguous strings of
> 1's and then halt. Let S be the set of all output tapes from these TM's.

  S is an infinite set which is also countable.

> Define another TM I call a comparator (CTM).
> CTM compares the input tape to its output tape.
> If the input tape has more 1's, 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.
>
> We let CTM read all the tapes in S.

  What do you mean "read all the tapes in S"? S has infinitely
many members. If CTM tries to "read" all the members of S, it
will never finish.

> What is on the output tape of CTS?

  Nothing -- CTM never halts, as it never finishes reading its
input tapes.

> The output of CTM must have a finite number of 1's.
> Every tape read by CTM was finite in length.
> The output of CTM has exactly one more 1 than
> some input tape in S.

  Non sequitur.

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

  Non sequitur.
  Surely you've had this explained to you in the past,
about how some infinities are bigger than others, and which
ones, and how? Check Google Groups if you haven't, or don't
remember -- I'm sure there's plenty of tutorial information
on there. Check sci.math's archives, too.

-Arthur

Relevant Pages