TY - BOOK

T1 - Reactive Turing machines

AU - Baeten, J.C.M.

AU - Luttik, B.

AU - Tilburg, van, P.J.A.

PY - 2011

Y1 - 2011

N2 - We propose reactive Turing machines, extending classical Turing machines with a process-theoretical notion of interaction. We show that every effective transition system is simulated up to branching bisimilarity by a reactive Turing machine, and that every computable transition system with a bounded branching degree is simulated up to divergence-preserving branching bisimilarity by a reactive Turing machine. We conclude from these results that there exist universal reactive Turing machines, and that the parallel composition of a finite number of (communicating) reactive Turing machines can be simulated by a single reactive Turing machine. We also establish a correspondence between reactive Turing machines and the process theory TCPtau, proving that a transition system can be simulated, up to branching bisimilarity, by a reactive Turing machine if, and only if, it is definable by a finite TCPtau-specification.

AB - We propose reactive Turing machines, extending classical Turing machines with a process-theoretical notion of interaction. We show that every effective transition system is simulated up to branching bisimilarity by a reactive Turing machine, and that every computable transition system with a bounded branching degree is simulated up to divergence-preserving branching bisimilarity by a reactive Turing machine. We conclude from these results that there exist universal reactive Turing machines, and that the parallel composition of a finite number of (communicating) reactive Turing machines can be simulated by a single reactive Turing machine. We also establish a correspondence between reactive Turing machines and the process theory TCPtau, proving that a transition system can be simulated, up to branching bisimilarity, by a reactive Turing machine if, and only if, it is definable by a finite TCPtau-specification.

M3 - Report

T3 - arXiv.org [cs.LO]

BT - Reactive Turing machines

PB - s.n.

ER -