On the executability of interactive computation

Bas Luttik, F. Yang

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

2 Citations (Scopus)
1 Downloads (Pure)

Abstract

The model of interactive Turing machines (ITMs) has been proposed to characterise which stream translations are interactively computable; the model of reactive Turing machines (RTMs) has been proposed to characterise which behaviours are reactively executable. In this article we provide a comparison of the two models. We show, on the one hand, that the behaviour exhibited by ITMs is reactively executable, and, on the other hand, that the stream translations naturally associated with RTMs are interactively computable. We conclude from these results that the theory of reactive executability subsumes the theory of interactive computability. Inspired by the existing model of ITMs with advice, which provides a model of evolving computation, we also consider RTMs with advice and we establish that a facility of advice considerably upgrades the behavioural expressiveness of RTMs: every countable transition system can be simulated by some RTM with advice up to a fine notion of behavioural equivalence.
Original languageEnglish
Title of host publicationPursuit of the Universal
Subtitle of host publicationProceedings of the 12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016).
EditorsArnold Beckmann, Laurent Bienvenue, Nataša Jonoska
PublisherSpringer
Pages312-322
Number of pages10
ISBN (Electronic)978-3-319-40189-8
ISBN (Print)978-3-319-40188-1
DOIs
Publication statusPublished - 2016
Event12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016) - Paris, France
Duration: 27 Jun 20161 Jul 2016
https://lipn.univ-paris13.fr/CIE2016/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9709

Conference

Conference12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016)
Abbreviated titleCIE2016
CountryFrance
CityParis
Period27/06/161/07/16
Internet address

Fingerprint Dive into the research topics of 'On the executability of interactive computation'. Together they form a unique fingerprint.

  • Cite this

    Luttik, B., & Yang, F. (2016). On the executability of interactive computation. In A. Beckmann, L. Bienvenue, & N. Jonoska (Eds.), Pursuit of the Universal: Proceedings of the 12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016). (pp. 312-322). (Lecture Notes in Computer Science; Vol. 9709). Springer. https://doi.org/10.1007/978-3-319-40189-8_32