On the executability of interactive computation

DOI10.1007/978-3-319-40189-8_32zbMATH Open1475.68131arXiv1601.01546OpenAlexW2225941034MaRDI QIDQ3188271FDOQ3188271

Authors: Bas Luttik, Fei Yang 

Publication date: 17 August 2016

Published in: Pursuit of the Universal (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1601.01546

Recommendations

• Reactive Turing machines
• Reactive Turing machines
• A theory of interactive computation
• Publication:4504007
• Executable behaviour and the \(\pi \)-calculus (extended abstract)

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Turing machines and related notions (03D10) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Reactive Systems
• Branching time and abstraction in bisimulation semantics
• On the executability of interactive computation
• A theory of interactive computation
• Branching Bisimilarity with Explicit Divergence
• A process-theoretic look at automata
• How We Think of Computing Today
• Reactive Turing machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Interactive Computation
• An Unsolvable Problem of Elementary Number Theory
• Title not available (Why is that?)

Cited In (9)

• Reactive Turing machines
• Turing machines, transition systems, and interaction
• Are there interactive protocols for co-NP languages?
• On the executability of interactive computation
• Title not available (Why is that?)
• Sequential composition in the presence of intermediate termination (extended abstract)
• The \(\pi\)-calculus is behaviourally complete and orbit-finitely executable
• Executable behaviour and the \(\pi \)-calculus (extended abstract)
• Proceedings of the workshop on the foundations of interactive computation (FinCo 2007), Braga, Portugal, March 31, 2007

This page was built for publication: On the executability of interactive computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188271)