Real-time solutions of the origin-crossing problem

Abstract

The n-dimensional origin-crossing language, On, is a language each of whose words describes a walk through n-dimensional space beginning and ending at the origin. For each n, On is real-time recognizable by an n-counter machine but not by any (n - 1)-counter machine. In contrast, for all n, On is real-time recognizable by a one-tape Turing machine. © 1968 Springer-Verlag New York Inc.