2019/02/03 by Holger Petersen, Petersen, Holger
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1902.00975
openalex publication_date 2019/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The power of real-time Turing machines using sublinear space is investigated. In contrast to a claim appearing in the literature, such machines can accept non-regular languages, even if working in deterministic mode. While maintaining a standard binary counter appears to be impossible in real-time, we present a guess and check approach that yields a binary representation of the input length. Based on this technique, we show that unary encodings of languages accepted in exponential time can be recognized by nondeterministic real-time Turing machines.