zbMATH — the first resource for mathematics

Actors and logical analysis of interactive systems. (English) Zbl 1276.68078
Goldin, Dina (ed.) et al., Proceedings of the workshop on the foundations of interactive computation (FInCo 2005), Edinburgh, UK, April 9, 2005. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 141, No. 5, 115-133 (2005).
Summary: Formalization in a logical theory can contribute to the foundational understanding of interactive systems in two ways. One is to provide language and principles for specification of and reasoning about such systems. The other is to better understand the distinction between sequential (Turing equivalent) computation and interactive computation using techniques and results from recursion theory and proof theory. In this paper we briefly review the notion of interaction semantics for actor systems, and report on work in progress to formalize this interaction model. In particular we have shown that the set-theoretic models of the formal interaction theory have greater recursion-theoretic complexity than analogous models of theories of sequential computation, using a well-known result from recursion theory.
For the entire collection see [Zbl 1273.68034].
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q60 Specification and verification (program logics, model checking, etc.)
03B70 Logic in computer science
03D80 Applications of computability and recursion theory
Full Text: Link