From: collins@newton.apple.com (Scott Collins)
Date: Tue, 26 Jul 94 12:44:50 PDT
To: cypherpunks@toad.com
Subject: No, each tape position cannot... (was Re: GUT and P=NP)
Message-ID: <9407261943.AA02688@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


  >Could I not let each position on the tape represent a real value in
  >[0...1]?

You could try!  But you would always omit values.  You can demonstrate this
with the `diagonal rule' or similar proofs.  Here's a simple one:

Take any two adjacent `positions' on the tape; Write out the decimal (or
binary) notation for the real values they represent (note, the
representations may be infinite).  Given two such strings that are not
identical, you can always find a string numerically `between' them (even if
both are infinite) as long as they are not identical.  E.g.,

      "0.12345"
  --->"0.123455"<----
      "0.12346"

Such a string is a real value you omitted.  Your tape, even if it is
infinite, is not the right order of infinity to model the Real numbers.

Scott Collins     | "Invention, my dear friends, is 93% perspiration,
                  |  6% electricity, 4% evaporation, and 2% butter-
  collins@acm.org |  scotch ripple."                   -- Willy Wonka
..................|..................................................
Apple Computer, Inc.  5 Infinite Loop, MS 305-2D  Cupertino, CA 95014
408.862.0540   fax:974.6094   R254(IL5-2N)   collins@newton.apple.com
.....................................................................
408.257.1746  1024:669687                         catalyst@netcom.com