### Samenvatting

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.

Originele taal-2 | Engels |
---|---|

Uitgeverij | s.n. |

Aantal pagina's | 28 |

Status | Gepubliceerd - 2011 |

### Publicatie series

Naam | arXiv.org [cs.LO] |
---|---|

Volume | 1104.1738 |

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

## Citeer dit

Baeten, J. C. M., Luttik, B., & Tilburg, van, P. J. A. (2011).

*Reactive Turing machines*. (arXiv.org [cs.LO]; Vol. 1104.1738). s.n.