Turing machines, transition systems, and interaction

2004/09/25 by Dina Goldin, Dina Q. Goldin, Scott A. Smolka +2 · 1 voice · 2 citations
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Distributed systems and fault tolerance

paper · doi:10.1016/j.ic.2004.07.002

openalex publication_date 2004/09/25 · crossref created 2004/09/25 · crossref issued 2004/11/01 · crossref published 2004/11/01 · crossref published-print 2004/11/01 · crossref deposited 2020/04/03 · openalex created_date 2025/10/10 · crossref indexed 2026/03/29 · openalex updated_date 2026/06/11

Citations

• Statecharts: a visual formalism for complex systems
• On Computable Numbers, with an Application to the Entscheidungsproblem

Cited by

• Composition of Interacting Computations
• In the beginning was game semantics

Discussions

• I'm asserting that pairwise sequential interactive computation is more expressive than any Turing machine incapable of representing its interaction history doi.org/10.1016/j.ic... [bsky, 0 points, 1 comments]