2012/07/30 by Nachum Dershowitz · 8 citations
Computer Science · #Algebra over a field #Axiom #Axiomatic system #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computation #Countable set #cs.LO #cs.PL #semigroups and automata theory
paper · pdf · doi:10.4204/eptcs.88.5
published in Electronic Proceedings in Theoretical Computer Science 88, 59-71 (Open Publishing Association) · In Proceedings DCM 2011, arXiv:1207.6821
openalex publication_date 2012/07/30 · arxiv created 2012/07/31 · arxiv updated 2012/08/14 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
Over the past two decades, Yuri Gurevich and his colleagues have formulated axiomatic foundations for the notion of algorithm, be it classical, interactive, or parallel, and formalized them in the new generic framework of abstract state machines. This approach has recently been extended to suggest a formalization of the notion of effective computation over arbitrary countable domains. The central notions are summarized herein.