Reactive Turing machines

J.C.M. Baeten, B. Luttik, P.J.A. Tilburg, van

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
13 Downloads (Pure)

Abstract

We propose reactive Turing machines (RTMs), extending classical Turing machines with a process-theoretical notion of interaction. We show that every effective transition system is simulated modulo branching bisimilarity by an RTM, and that every computable transition system with a bounded branching degree is simulated modulo divergence-preserving branching bisimilarity. 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 RTMs and the process theory.
Original languageEnglish
Title of host publicationFundamentals of Computation Theory (18th International Symposium, FCT'11, Oslo, Norway, August 22-25, 2011. Proceedings)
EditorsO. Owe, M. Steffen, J.A. Telle
Place of PublicationBerlin
PublisherSpringer
Pages348-359
ISBN (Print)978-3-642-22952-7
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6914
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Reactive Turing machines'. Together they form a unique fingerprint.

  • Cite this

    Baeten, J. C. M., Luttik, B., & Tilburg, van, P. J. A. (2011). Reactive Turing machines. In O. Owe, M. Steffen, & J. A. Telle (Eds.), Fundamentals of Computation Theory (18th International Symposium, FCT'11, Oslo, Norway, August 22-25, 2011. Proceedings) (pp. 348-359). (Lecture Notes in Computer Science; Vol. 6914). Springer. https://doi.org/10.1007/978-3-642-22953-4_30