Re: Cardinality of Set of Computable Numbers?

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

Date: Tue, 30 Dec 2003 13:29:33 -0500 (EST)

[Sorry, sci.logic.]

On Tue, 30 Dec 2003, Russell Easterly wrote:
>
> "|-|erc" <trymyform@wwwadamskingdom.com> wrote in message
> >
> > Haven't you just proven all finite lists are incomplete?
>
> Pretty much.

  Well, duh. The set of natural numbers is infinite. Thus any
finite list of natural numbers will by definition be incomplete.
For example, the list (1, 2, 3, 5, 6) is missing the natural
numbers 0, 4, 7, 8, 9,... and so on.
  However, the list of natural numbers (0, 1, 2, 3,...) [and so on
forever] is not missing any natural number; if you go far enough
out, you'll find any natural number you care to look for.

> I never like to give the same proof twice.
> Here is a new one the uses two TMs and one tape.
>
> Assume there is a TM that produces the string:
>
> 010110111011110111110...
>
> This string is infinite in length and contains an
> unary representation of every natural number
> followed by one 0.

  Correct.

> I can define a second TM to read this tape
> and write to this tape a finite number of 1's
> that is not on the tape before the second TM
> processes it.

  Obviously, you cannot. The tape *already* contains, quote,
"every natural number." There are no natural numbers left that
aren't on the tape yet. Your statement is nonsensical.

[skip algorithmic definition of the machine]
> This TM will erase every zero on the tape
> except the "last" one.

  Define "last", please. Remember, the tape contains
an infinite number of zeroes.

-Arthur

Relevant Pages

  • Re: Cardinality of Set of Computable Numbers?
    ... > Haven't you just proven all finite lists are incomplete? ... Here is a new one the uses two TMs and one tape. ... Assume there is a TM that produces the string: ... State 1 - find another zero ...
    (comp.theory)
  • Re: Delete a file from a tape?
    ... I have a tape with a few files (backup savesets). ... -SYSTEM-F-OPINCOMPL, operation is incomplete ...
    (comp.os.vms)
  • IRS Backup Withholding
    ... the IRS has concluded that there is incomplete ... or incorrect data we sent them for 1099 sent out last year and this ... I do not have a tape drive that reads this type of cartridge... ...
    (misc.taxes)