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