From: Patrick Juola <juola@suod.cs.colorado.edu>
Date: Tue, 26 Jul 94 10:03:03 PDT
To: cypherpunks@toad.com
Subject: Re: GUT and P=NP
Message-ID: <199407261700.LAA22817@suod.cs.colorado.edu>
MIME-Version: 1.0
Content-Type: text/plain


  
  nzook@fireant.ma.utexas.edu writes:
   > Let f be a function from the integers to [0,1].  Note that the
   > Turing tape has precisely one space for each integer, so this
   > function cooresponds to your idea.

  m5@vail.tivoli.com (Mike McNally) responds
  Can you (without being an asshole) explain why exactly each tape
  position may contain only a simple integer?  It's perfectly reasonable
  to define the tape alphabet to be an arbitrary set; can the set not
  be uncountably infinite?  If not, why not?

Well, the "standard" in all the language stuff precludes infinite alphabets
just as it precludes infinite-length programs.  In fact, it's fairly
easy to demonstrate an equivalence betweeen the two.  I've been working
off-and-on (mostly off) for the past ten years or so trying to rewrite
Hopcroft and Ullman for the case of infinite alphabets of various
sizes, and in general, *none* of the theorems hold for problems
describably in a single input symbol.

From a practical standpoint, of course, it's even harder to build an
infinite tape with an uncountable alphabet than to build an infinite
binary tape.  More generally, the problems of *programming* such a
machine are immense -- there are some very important real world
continuity/expressability properties about what sort of symbols can
be transformed into what other symbols.  Without highly discontinuous
and chaotic transformations that are informationally incompressible,
you don't get any more computational power than a standard TM.

	- kitten