2012/07/30 by Nachum Dershowitz, Evgenia Falkovich · 6 citations
Computer Science · #Algorithm #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computation #Computer science #Description number #Finite-state machine #Graph #Probabilistic Turing machine #Programming language #State (computer science) #Super-recursive algorithm #Theoretical computer science #Turing #Turing machine #Turing machine examples #Universal Turing machine #cs.CC #cs.LO #semigroups and automata theory
paper · pdf · doi:10.4204/eptcs.88.6
published in Electronic Proceedings in Theoretical Computer Science 88, 72-78 (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/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We prove the Extended Church-Turing Thesis: Every effective algorithm can be efficiently simulated by a Turing machine. This is accomplished by emulating an effective algorithm via an abstract state machine, and simulating such an abstract state machine by a random access machine, representing data as a minimal term graph.