On the executability of interactive computation

Bas Luttik; F. Yang

doi:10.1007/978-3-319-40189-8_32

On the executability of interactive computation

Bas Luttik
, F. Yang

Formal System Analysis

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

3 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 language	English
Title of host publication	Pursuit of the Universal
Subtitle of host publication	Proceedings of the 12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016).
Editors	Arnold Beckmann, Laurent Bienvenue, Nataša Jonoska
Publisher	Springer
Pages	312-322
Number of pages	10
ISBN (Electronic)	978-3-319-40189-8
ISBN (Print)	978-3-319-40188-1
DOIs	https://doi.org/10.1007/978-3-319-40189-8_32
Publication status	Published - 2016
Event	12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016) - Paris, France Duration: 27 Jun 2016 → 1 Jul 2016 https://lipn.univ-paris13.fr/CIE2016/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9709

Conference

Conference	12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016)
Abbreviated title	CIE2016
Country/Territory	France
City	Paris
Period	27/06/16 → 1/07/16
Internet address	https://lipn.univ-paris13.fr/CIE2016/

Access to Document

10.1007/978-3-319-40189-8_32

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

@inproceedings{b479a22c3c254877ae7164f2ff78e036,

title = "On the executability of interactive computation",

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.",

author = "Bas Luttik and F. Yang",

year = "2016",

doi = "10.1007/978-3-319-40189-8\_32",

language = "English",

isbn = "978-3-319-40188-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "312--322",

editor = "Arnold Beckmann and Laurent Bienvenue and Nata{\v s}a Jonoska",

booktitle = "Pursuit of the Universal",

address = "Germany",

note = "12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016), CIE2016 ; Conference date: 27-06-2016 Through 01-07-2016",

url = "https://lipn.univ-paris13.fr/CIE2016/",

}

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).. Lecture Notes in Computer Science, vol. 9709, Springer, pp. 312-322, 12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016), Paris, France, 27/06/16. https://doi.org/10.1007/978-3-319-40189-8_32

On the executability of interactive computation. / Luttik, Bas; Yang, F.
Pursuit of the Universal: Proceedings of the 12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016).. ed. / Arnold Beckmann; Laurent Bienvenue; Nataša Jonoska. Springer, 2016. p. 312-322 (Lecture Notes in Computer Science; Vol. 9709).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the executability of interactive computation

AU - Luttik, Bas

AU - Yang, F.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-40189-8_32

DO - 10.1007/978-3-319-40189-8_32

M3 - Conference contribution

SN - 978-3-319-40188-1

T3 - Lecture Notes in Computer Science

SP - 312

EP - 322

BT - Pursuit of the Universal

A2 - Beckmann, Arnold

A2 - Bienvenue, Laurent

A2 - Jonoska, Nataša

PB - Springer

T2 - 12th Conference on Computability in Europe, Paris, France, June 27 - July 1, 2016 (CiE 2016)

Y2 - 27 June 2016 through 1 July 2016

ER -

On the executability of interactive computation

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this