Abstract
We enhance the notion of a computation of the classical theory of computing with the notion of interaction. In this way, we enhance a Turing machine as a model of computation to a Reactive Turing Machine that is an abstract model of a computer as it is used nowadays, always interacting with the user and the world.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baeten, J.C.M.: Models of Computation: Automata and Processes. Technische Universiteit Eindhoven, Syllabus 2IT15 (2010)
Baeten, J.C.M., Basten, T., Reniers, M.A.: Process Algebra (Equational Theories of Communicating Processes). Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge (2009)
Baeten, J.C.M., Corradini, F., Grabmayer, C.A.: A characterization of regular expressions under bisimulation. Journal of the ACM 54(2):6, 1–28 (2007)
Baeten, J.C.M., Cuijpers, P.J.L., Luttik, B., van Tilburg, P.J.A.: A process-theoretic look at automata. In: Arbab, F., Sirjani, M. (eds.) FSEN 2009. LNCS, vol. 5961, pp. 1–33. Springer, Heidelberg (2010)
Baeten, J.C.M., Cuijpers, P.J.L., van Tilburg, P.J.A.: A context-free process as a pushdown automaton. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, pp. 98–113. Springer, Heidelberg (2008)
Baeten, J.C.M., Luttik, B., van Tilburg, P.J.A.: Reactive Turing machines. Draft (2010)
Baeten, J., Luttik, B., Muller, T., van Tilburg, P.: Expressiveness modulo bisimilarity of regular expressions with parallel composition. In: Fröschle, S., Valencia, F.D. (eds.) Proceedings EXPRESS 2010, number xx in EPTCS, pp. 229–243 (2010)
Basten, T.: Branching bisimilarity is an equivalence indeed! Information Processing Letters 58(3), 141–147 (1996)
van Glabbeek, R.J.: What is Branching Time Semantics and why to use it? Bulletin of the EATCS 53, 190–198 (1994)
van Glabbeek, R.J.: The Linear Time – Branching Time Spectrum I. In: Bergstra, J.A., Ponse, A., Smolka, S.A. (eds.) Handbook of Process Algebra, pp. 3–99. Elsevier, Amsterdam (2001)
van Glabbeek, R.J., Weijland, W.P.: Branching time and abstraction in bisimulation semantics. Journal of the ACM 43(3), 555–600 (1996)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Pearson, London (2006)
Milner, R.: A Calculus of Communication Systems. LNCS, vol. 92. Springer, Heidelberg (1980)
Moller, F.: Infinite results. In: Montanari, U., Sassone, V. (eds.) CONCUR 1996. LNCS, vol. 1119, pp. 195–216. Springer, Heidelberg (1996)
Park, D.M.R.: Concurrency and automata on infinite sequences. In: Deussen, P. (ed.) GI-TCS 1981. LNCS, vol. 104, pp. 167–183. Springer, Heidelberg (1981)
Plotkin, G.D.: A structural approach to operational semantics. J. Log. Algebr. Program., 60-61, 17–139 (2004)
Turing, A.M.: On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society 42(2), 230–265 (1936)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baeten, J.C.M., Luttik, B., van Tilburg, P. (2011). Computations and Interaction. In: Natarajan, R., Ojo, A. (eds) Distributed Computing and Internet Technology. ICDCIT 2011. Lecture Notes in Computer Science, vol 6536. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19056-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-19056-8_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19055-1
Online ISBN: 978-3-642-19056-8
eBook Packages: Computer ScienceComputer Science (R0)