Register computations on ordinals

Slides

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 s₀ has lower speed that state s₁ if an automaton in state s₁ positioned to the left of an automaton in state s₀ 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.

References

Bissell-Siders [2007]

R. Bissell-Siders. Ehrenfeucht-Fraïssé games on linear orders. In R. d. Q. Daniel Levant, editor, Logic, Language, Information and Computation, number 4576 in Lecture Notes in Computer Science, pages 72–82, 2007.

Durand-Lose [2006]

J. Durand-Lose. Reversible conservative rational abstract geometrical computation is Turing-universal. In A. Beckmann and J. V. Tucker, editors, Logical Approaches to Computational Barriers, 2nd Conf. Computability in Europe (CiE ’06), number 3988 in LNCS, pages 163–172. Springer, 2006.

Durand-Lose [1998]

J. Durand-Lose. About the universality of the billiard ball model. In M. Margenstern, editor, Universal Machines and Computations (UMC ’98), volume 2, pages 118–133. Université de Metz, 1998.

Flocchini et al. [2008]

P. Flocchini, D. Ilcinkas, and N. Santoro. Ping pong in dangerous graphs: Optimal black hole search with pure tokens. Number 5218 in LNCS, pages 227–241. Springer, 2008.

Koepke and Bissell-Siders [2008]

P. Koepke and R. Bissell-Siders. Register computations on ordinals. Archive for Mathematical Logic, 47 (6): 529–548, 2008.

This document was translated from L^AT_EX by H^EV^EA.