1968/07/01 by Juris Hartmanis, H. Shank · 1 citation
Computer Science · Mathematics · #Algorithm #Automata theory #Automaton #Combinatorics #Computability, Logic, AI Algorithms #Computer science #Deterministic automaton #Discrete mathematics #Finite-state machine #Logic, programming, and type systems #Mathematics #Prime number #Pushdown automaton #Quantum finite automata #Set (abstract data type) #Theoretical computer science #semigroups and automata theory #ω-automaton
paper · pdf · doi:10.1145/321466.321470
openalex publication_date 1968/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
A study of the problem of recognizing the set of primes by automata is presented. A simple algebraic condition is derived which shows that neither the set of primes nor any infinite subset of the set of primes can be accepted by a pushdown or finite automaton. In view of this result an interesting open problem is to determine the “weakest” automaton which can accept the set of primes. It is shown that the linearly bounded automaton can accept the set of primes, and it is conjectured that no automaton whose memory grows less rapidly can recognize the set of primes. One of the results shows that if this conjecture is true, it cannot be proved by the use of arguments about the distribution of primes, as described by the Prime Number Theorem. Some relations are established between two classical conjectures in number theory and the minimal rate of memory growth of automata which can recognize the set of primes.