Reactive Turing machines

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

10 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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. We establish a correspondence between executability and finite definability in a simple process calculus. Finally, we establish that RTMs are at least as expressive as persistent Turing machines.
Originele taal-2Engels
Pagina's (van-tot)143-166
Aantal pagina's24
TijdschriftInformation and Computation
Volume231
DOI's
StatusGepubliceerd - 2013

Vingerafdruk

Duik in de onderzoeksthema's van 'Reactive Turing machines'. Samen vormen ze een unieke vingerafdruk.

Citeer dit