2000/07/01 by Yuri Gurevich · 7 citations
Computer Science · #Computability, Logic, AI Algorithms #Logic, Reasoning, and Knowledge #Distributed systems and fault tolerance
paper · pdf · doi:10.1145/343369.343384
openalex publication_date 2000/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
We examine sequential algorithms and formulate a sequential-time postulate, an abstract-state postulate, and a bounded-exploration postulate . Analysis of the postulates leads us to the notion of sequential abstract-state machine and to the theorem in the title. First we treat sequential algorithms that are deterministic and noninteractive. Then we consider sequential algorithms that may be nondeterministic and that may interact with their environments.