On the executability of interactive computation

DOI10.1007/978-3-319-40189-8_32MaRDI QIDQ3188271zbMATH OpenOpenAlexFDO

Authors Bas Luttik, Fei Yang

Publication date 17 August 2016

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

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1687054 (Why is no real title available?)
• scientific article; zbMATH DE number 2080910 (Why is no real title available?)
• scientific article; zbMATH DE number 1759398 (Why is no real title available?)
• A process-theoretic look at automata
• A theory of interactive computation
• An Unsolvable Problem of Elementary Number Theory
• Branching Bisimilarity with Explicit Divergence
• Branching time and abstraction in bisimulation semantics
• How We Think of Computing Today
• Interactive Computation
• On the executability of interactive computation
• Reactive Systems
• Reactive Turing machines

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
• scientific article; zbMATH DE number 7243676 (Why is no real title available?)
• 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)