Re: Cardinality of Set of Computable Numbers?

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 12/27/03 

Date: 27 Dec 2003 07:05:23 -0800

Russell Easterly says...

>The output of a RM has the following form:
>There is a finite, possibly empty initial string that is written once,
>and a finite, never empty repeating string that is written over and over.
>A computable number can be written as the initial string followed by
>the repeating string in parenthesis.

>Let x initally be (0).
>If s has the form 111...111(0) and the length of the initial segment of s
>is longer or equal to the length of the initial segment of x then take the
>initial segment of s, append a 1, and make this new string the initial
>segment of x.
>
>Examples:
>
>s x
>(0) 1(0)
>1(0) 11(0)
>11(0) 111(0)
>
>Prove that x differs from every member of S.

You haven't given the definition of x. You've listed
three different values for x: 1(0), 11(0), 111(0). Which
one is x? Perhaps you are saying that x is some kind
of limit of the sequence

    1(0)
    11(0)
    111(0)

But how do you prove that the limit exists? How do you
prove that the limit is one of your RM computable numbers?

This is in contrast to the usual diagonalization
procedure, which produces a convergent sequence
of reals. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: pointers and beginnings of arrays
    ... If p started at the beginning of the string, ... reg is near the end of the segment, ... adding 1000 puts it one byte past the last valid object -- ... pointing to the first valid object, ...
    (comp.lang.c)
  • RE: Split function in query
    ... Function SplitString(Main As String, Delimiter As String, Segment As Integer) ... >> Is Split invalid in SQL? ...
    (microsoft.public.access.queries)
  • Re: String extrahieren
    ... Ich lese eine txt- Datei in einen String ... solche Segment würde ich gerne auf einfache Art und Weise ... Dim strDate As String ... Dim lngI As Long ...
    (microsoft.public.de.excel)
  • [PATCH 1/2] ROMFS: romfs_lookup() shouldnt be doing a partial name comparison
    ... romfs_lookupshould be using a routine akin to strcmpon the backing store, ... * compare a string to one in a romfs image on MTD ... size_t len, segment; ... if (ret < 0) ...
    (Linux-Kernel)
  • Re: Cardinality of Set of Computable Numbers?
    ... >> segment of s is longer or equal to the length of the initial ... >> Prove that x differs from every member of S. ... >> x differs from every s that does not end with. ... each binary string represents a natural number in base 1. ...
    (comp.theory)