(Kyoto University)

For computation over real numbers and more generally over topological spaces, we need to consider two things. One is that each point is represented as an infinite data, and the other thing is that the space itself has a connected topological structure.In this talk, we first present an approach to real number computation based on modified Gray expansion. With this approach, the unit interval is represented in the space of sequences with bottoms, and such a sequence is input and output by an IM2-machine, which make multiple-head indeterministic stream access to the tapes.

This expansion is defined through the dynamical system of the tent function and thus it has a recursive structure which enables recursive function definitions for IM2-machines.

Next, we study its generalizations to computation over compact Hausdorff spaces in general and consider requirements on dynamical systems so that it induces expansions suitable for such recursive function definitions.

Finally, we give characterization of such dynamical systems for the two-dimensional case.

Robert Recorde Room

Department of Computer Science