Register computations on ordinalsRyan Bissell-SidersUniversity of Helsinki |
We wish to draw some connections between the expressibility of continuous computation and infinitary computations on ordinals. We study a team of automata, that is, a collection of automata which only change state when they collide. We study their behavior only on a linear order, though others have studied their behavior on graphs. A discrete automata moves, at the next timestep, to a location definable in the model, with the current location as a parameter (e.g., “go to the successor, or go to the first limit point”). For a team of continuous automata, we define a ordering relation speed on their states, so that state s0 has lower speed that state s1 if an automaton in state s1 positioned to the left of an automaton in state s0 must eventually collide. We allow the automata to mark the sites of their collisions, thereby forming an ordered set of events which further automata can use to define their movement.
This definition encompasses many systems of computation which are Turing-universal or stronger, including abstract geometric computation (signal machines with rational linear speeds), one-dimensional billiards, and ordinal register machines. We have taken the name team automata after reading about teams of automata which try to explore an arbitrary graph or mark “black holes” in the graph. More lightheartedly, the interaction of slow-moving, faster-moving, and very-fast automata seems to be played out in many war games, such as chess and shogi. However, these games would only become teams of automata under our definition if all pieces could move simultaneously.
We consider team automata moving on the continuum and marking their events, and we ask that the computation be robust – i.e., insensitive to initial perturbations. We bound the expressiveness of these machines, comparing them to ordinal register machines.
This document was translated from LATEX by HEVEA.