
arXiv: 1104.1738
We propose reactive Turing machines (RTMs), extending classical Turing machines with a process-theoretical notion of interaction, and use it to define a notion of executable transition system. We show that every computable transition system with a bounded branching degree is simulated modulo divergence-preserving branching bisimilarity by an RTM, and that every effective transition system is simulated modulo the variant of branching bisimilarity that does not require divergence preservation. We conclude from these results that the parallel composition of (communicating) RTMs can be simulated by a single RTM. We prove that there exist universal RTMs modulo branching bisimilarity, but these essentially employ divergence to be able to simulate an RTM of arbitrary branching degree. We also prove that modulo divergence-preserving branching bisimilarity there are RTMs that are universal up to their own branching degree. Finally, we establish a correspondence between executability and finite definability in a simple process calculus.
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Formal Languages and Automata Theory (cs.FL), Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Computer Science - Formal Languages and Automata Theory, Models of computation (Turing machines, etc.), 004, Logic in Computer Science (cs.LO), Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Formal Languages and Automata Theory (cs.FL), Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Computer Science - Formal Languages and Automata Theory, Models of computation (Turing machines, etc.), 004, Logic in Computer Science (cs.LO), Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 17 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
