On the executability of interactive computation

Bas Luttik, F. Yang

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)
1 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelPursuit of the Universal
SubtitelProceedings of the 12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016).
RedacteurenArnold Beckmann, Laurent Bienvenue, Nataša Jonoska
UitgeverijSpringer
Pagina's312-322
Aantal pagina's10
ISBN van elektronische versie978-3-319-40189-8
ISBN van geprinte versie978-3-319-40188-1
DOI's
StatusGepubliceerd - 2016
Evenement12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016) - Paris, Frankrijk
Duur: 27 jun 20161 jul 2016
https://lipn.univ-paris13.fr/CIE2016/

Publicatie series

NaamLecture Notes in Computer Science
UitgeverijSpringer
Volume9709

Congres

Congres12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016)
Verkorte titelCIE2016
LandFrankrijk
StadParis
Periode27/06/161/07/16
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'On the executability of interactive computation'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

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