Modelling interactive computing systems: Do we have a good theory of what computers are?
Article Sidebar
Main Article Content
Abstract
Computers are increasingly interactive. They are no more transformational systems producing a final output after a finite execution. Instead, they continuously react in time to external events that modify the course of computing execution. While philosophers have been interested in conceptualizing computers for a long time, they seem to have paid little attention to the specificities of interactive computing. We propose to tackle this issue by surveying the literature in theoretical computer science, where one can find explicit proposals for a model of interactive computing. In that field, the formal modelling of interactive computing systems has been brought down to whether the new interaction models are reducible to Turing Machines. There are three areas where interaction models are framed. The comparison between TMs and interactive system models is at stake in all of them. These areas are namely some works on concurrency by Milner, on Reactive Turing Machines, and on interaction as a new computing paradigm. For each of the three identified models, we present its motivation, sum up its account for interaction and its legacy, and point out issues regarding the understanding of computers. The survey shows difficulties for epistemologists. The reason is that these analyses focus on the formal equivalence between interactive models of computation and classic ones. Such a project is different from addressing how a computing machine can be interactive: in other words, which mechanisms allow it.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
Andersen, H.R., Mřrk, S. and Sřrensen, M.U., 1997. A universal reactive machine. In: A. Mazurkiewicz and J. Winkowski, eds. Concur ’97: concurrency theory. concur 1997 [Online]. Vol. 1243, Lecture notes in computer science. Berlin; Heidelberg: Springer, pp.89–103. https://doi.org/10.1007/3-540-63141-0_7.
Arbach, Y., Karcher, D., Peters, K. and Nestmann, U., 2015. Dynamic causality in event structures. In: S. Graf and M. Viswanathan, eds. Formal techniques for distributed objects, components, and systems [Online]. Vol. 9039, Lecture notes in computer science, pp.83–97. https://doi.org/10.1007/978-3-319-19195-9_6.
Aspray, W., 1990. John von neumann and the origins of modern computing. Cambridge, MA: MIT Press.
Backus, J., 1978. Can programming be liberated from the von Neumann style? Communications of the ACM, 21(8), pp.613–641.
Baeten, J.C., Luttik, B. and Tilburg, P.V., 2012. Turing meets milner. Concur’12: proceedings of the 23rd international conference on concurrency theory [Online], Lecture notes in computer science. Berlin; Heidelberg: Springer, pp.1–20. https://doi.org/10.1007/978-3-642-32940-1_1.
Baeten, J.C., Luttik, B. and Tilburg, P.V., 2013. Reactive Turing machines. In: O. Owe, M. Steffen and J. Telle, eds. Fct 2011: fundamentals of computation theory [Online], Lecture notes in computer science. Berlin; Heidelberg: Springer, pp.348–359. https://doi.org/10.1016/j.ic.2013.08.010.
Balcázar, J.L., Díaz, J. and Gabarró, J., 1995. Structural complexity I. [Online]. Second Edition, Texts in Theoretical Computer Science. An EATCS Series. Berlin; Heidelberg: Springer. https://doi.org/10.1007/978-3-642-97062-7.
Baldan, P., Corradini, A. and Montanari, U., 2001. Contextual petri nets, asymmetric event structures, and processes. Information and Computation [Online], 171(1), pp.1–49. https://doi.org/10.1006/inco.2001.3060.
Basman, A., Tchernavskij, P., Bates, S. and Beaudouin-Lafon, M., 2018. An anatomy of interaction: co-occurrences and entanglements. Conference companion of the 2nd international conference on art, science, and engineering of programming [Online]. Association for Computing Machinery, pp.188–196. https://doi.org/10.1145/3191697.3214328.
Beaudouin-Lafon, M., 2006. Human-computer interaction. In: D. Goldin, S.A. Smolka and P. Wegner, eds. Interactive computation: the new paradigm [Online]. Berlin; Heidelberg: Springer, pp.227–254. https://doi.org/10.1007/3-540-34874-3_10.
Bielecki, A., 2019. Models of neurons and perceptrons: selected problems and challenges [Online]. Vol. 770, Studies in Computational Intelligence. Springer International Publishing. https://doi.org/10.1007/978-3-319-90140-4.
Cockshott, P. and Michaelson, G., 2007. Are there new models of computation? Reply to Wegner and Eberbach. Computer Journal [Online], 50(2), pp.232–247. https://doi.org/10.1093/comjnl/bxl062.
Copeland, B.J., 2002. Hypercomputation. Minds and Machines [Online], 12, pp.461–502. https://doi.org/10.1023/A:1021105915386.
Copeland, B.J. and Shagrir, O., 2011. Do accelerating Turing machines compute the uncomputable? Minds and Machines [Online], 21, pp.221–239. https://doi.org/10.1007/s11023-011-9238-y.
Daylight, E.G., 2014. A Turing tale. Communications of the ACM [Online], 57(10), pp.36–38. https://doi.org/10.1145/2629499.
Dearden, A.M. and Harrison, M.D., 1997. Abstract models for HCI. International Journal of Human Computer Studies [Online], 46(1), pp.151–177. https://doi.org/10.1006/ijhc.1996.0087.
Dodig-Crnkovic, G., 2011. Significance of models of computation, from Turing model to natural computation. Minds and Machines [Online], 21, pp.301–322. https://doi.org/10.1007/s11023-011-9235-1.
Eberbach, E., Goldin, D. and Wegner, P., 2004. Turing’s ideas and models of computation. In: C. Teuscher, ed. Alan turing: life and legacy of a great thinker [Online]. Berlin; Heidelberg: Springer, pp.159–194. https://doi.org/10.1007/978-3-662-05642-4_7.
Glabbeek, R.V. and Plotkin, G., 2004. Event structures for resolvable conflict. 29th international symposium on mathematical foundations of computer [Online]. Vol. 3153, Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics). Berlin; Heidelberg: Springer, pp.550–561. https://doi.org/10.1007/978-3-540-28629-5_42.
Glennan, S., 2002. Rethinking mechanistic explanation. Philosophy of Science [Online], 69(S3), pp.342–353. https://doi.org/10.1086/341857.
Godfrey, M.D. and Hendry, D.F., 1993. The computer as von neumann planned it. IEEE Annals of the History of Computing [Online], 15(1), pp.11–21. https://doi.org/10.1109/85.194088.
Goldin, D., 2000. Persistent Turing machines as a model of interactive computation. In: K. Schewe and B. Thalheim, eds. Foundations of Information and Knowledge Systems. FoIKS 2000 [Online]. Vol. 1762, Lecture notes in computer science. Berlin; Heidelberg: Springer, pp.116–135. https://doi.org/10.1007/3-540-46564-2_8.
Goldin, D., Smolka, S.A., Attie, P.C. and Sonderegger, E.L., 2004. Turing machines, transition systems, and interaction. Information and Computation [Online], 194(2), pp.101–128. https://doi.org/https://doi.org/10.1016/j.ic.2004.07.002.
Goldin, D. and Wegner, P., 2008. The interactive nature of computing: Refuting the strong Church-Turing thesis. Minds and Machines [Online], 18, pp.17–38. https://doi.org/10.1007/s11023-007-9083-1.
Goldin, D., Wegner, P. and Smolka, S.A., 2006. Interactive computation: the new paradigm [Online]. Berlin; Heidelberg: Springer. https://doi.org/10.1007/3-540-34874-3.
Haigh, T. and Priestley, M., 2020. Historical reflections von neumann thought turing’s universal machine was ’simple and neat.’ but that didn’t tell him how to design a computer. Communications of the ACM [Online], 63(1), pp.26–32. https://doi.org/10.1145/3372920.
Harel, D. and Pnueli, A., 1985. On the development of reactive systems. In: K. Apt, ed. Logics and models of concurrent systems [Online]. Vol. 13, Nato asi series. Berlin; Heidelberg: Springer, pp.477–498. https://doi.org/10.1007/978-3-642-82453-1_17.
Hartmanis, J., 1994. Turing award lecture on computational complexity and the nature of computer science. Communications of the ACM [Online], 37(10), pp.37–43. https://doi.org/10.1145/194313.214781.
Hornbaek, K. and Oulasvirta, A., 2017. What is interaction? Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems [Online]. New York, NY: Association for Computing Machinery, pp.5040–5052. https://doi.org/10.1145/3025453.3025765.
ISO, 2018. Ergonomics of human-system interaction. part 11: usability: definitions and concepts. ISO 9241-11:2018.
Klein, C., 2020. Polychrony and the process view of computation. Proceedings of the 2018 Biennial Meeting of the Philosophy of Science Association. Part II [Online]. Vol. 87, 5, pp.1140–1149. https://doi.org/10.1086/710613.
Knuth, D.E., 1968. The art of computer programming, vol.1: fundamental algorithms. Boston; etc.: Addison-Wesley.
Kycia, R. and Niemczynowicz, A., 2020. Information and physics. Philosophical Problems in Science (Zagadnienia Filozoficzne w Nauce) [Online], (69), pp.237–252. Available at: <https://zfn.edu.pl/index.php/zfn/article/view/513>.
Lee, E.A., 2017. Fundamental limits of cyber-physical systems modeling. ACM Transactions on Cyber-Physical Systems [Online], 1(1), pp.1–26. https://doi.org/10.1145/2912149.
Lee, E.A., 2020. Plato and the nerd [Online]. MIT Press. https://doi.org/10.7551/mitpress/11180.001.0001.
Lee, E.A. and Neuendorffer, S., 2006. Concurrent models of computation for embedded software. System-on-Chip: Next Generation Electronics [Online]. https://doi.org/10.1049/PBCS018E_ch7.
Lee, E.A. and Sangiovanni-Vincentelli, A., 1998. A framework for comparing models of computation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems [Online]. https://doi.org/10.1109/43.736561.
Luttik, B. and Yang, F., 2016. On the executability of interactive computation. In: A. Beckmann, L. Bienvenu and N. Jonoska, eds. Pursuit of the universal. cie 2016 [Online]. Vol. 9709, Lecture notes in computer science. Cham: Springer, pp.312–322. https://doi.org/10.1007/978-3-319-40189-8_32.
Machamer, P., Darden, L. and Craver, C.F., 2000. Thinking about mechanisms. Philosophy of Science [Online], 67(1), pp.1–25. https://doi.org/10.1086/392759.
MacLennan, B., 2003. Transcending Turing computability. Minds and Machines [Online], 13, pp.3–22. https://doi.org/10.1023/A:1021397712328.
MacLennan, B., 2009. Super-Turing or non-Turing? extending the concept of computation. International Journal of Unconventional Computing, 5(3-4), pp.369–387.
Manna, Z. and Pnueli, A., 1992. The temporal logic of reactive and concurrent systems [Online]. Springer. https://doi.org/10.1007/978-1-4612-0931-7.
Martin, A., Magnaudet, M. and Conversy, S., forthcoming. Computers as interactive machines: Can we build an explanatory abstraction? Minds and Machines.
Milner, R., 1975. Processes: A Mathematical Model of Computing Agents. In: H.E. Rose and J.C. Shepherdson, eds. Studies in Logic and the Foundations of Mathematics [Online]. Vol. 80, Logic Colloquium ’73. Elsevier, pp.157–173. https://doi.org/10.1016/S0049-237X(08)71948-7.
Milner, R., 1982. Four combinators for concurrency. Proceedings of the annual acm symposium on principles of distributed computing [Online], Podc ’82. New York, NY: Association for Computing Machinery, pp.104–110. https://doi.org/10.1145/800220.806687.
Milner, R., 1983. Calculi for synchrony and asynchrony. Theoretical Computer Science [Online]. https://doi.org/10.1016/0304-3975(83)90114-7.
Milner, R., 1993. Elements of interaction: Turing Award Lecture. Communications of the ACM [Online], 36(1), pp.78–89. https://doi.org/10.1145/151233.151240.
Milner, R., 1999. Communicating and mobile systems: the pi-calculus. Cambridge: Cambridge University Press.
Milner, R., 2006. Turing, computing and communication. In: Interactive Computation: The New Paradigm [Online]. Ed. by D. Goldin, S.A. Smolka and P. Wegner. Berlin; Heidelberg: Springer, pp.1–8. https://doi.org/10.1007/3-540-34874-3_1.
Milner, R., 2009. The space and motion of communicating agents. Cambridge: Cambridge University Press. https://doi.org/10.1017/CBO9780511626661.
Miłkowski, M., 2011. Beyond formal structure: a mechanistic perspective on computation and implementation. Journal of Cognitive Science, 12, pp.359–379.
Miłkowski, M., 2014. Computational mechanisms and models of computation. Philosophia Scientiae [Online], 18(3), pp.215–228. https://doi.org/10.4000/philosophiascientiae.1019.
Miłkowski, M., 2016. A mechanistic account of computational explanation in cognitive science and computational neuroscience. In: V.C. Müller, ed. Computing and Philosophy: Selected Papers from IACAP 2014 [Online]. Vol. 375. Springer International Publishing, pp.191–205. https://doi.org/10.1007/978-3-319-23291-1_13.
Mol, L.D., 2018. Turing machines. Stanford Encyclopedia [Online]. Available at: <https://plato.stanford.edu/entries/turing-machine/>.
Myers, B., 1994. Challenges of HCI design and implementation. Interactions [Online]. https://doi.org/10.1145/174800.174808.
Nielsen, M., Plotkin, G. and Winskel, G., 1981. Petri nets, event structures and domains, part I. Theoretical Computer Science [Online], 13(1), pp.85–108. https://doi.org/10.1016/0304-3975(81)90112-2.
Nisan, N. and Schocken, S., 2005. The Elements of Computing Systems: Building a Modern Computer from First Principles. Cambridge: MIT Press.
Petri, C., 1980. Introduction to general net theory. In: W. Brauer, ed. Net theory and applications [Online]. Vol. 84, Lecture notes in computer science. Berlin; Heidelberg: Springer. https://doi.org/10.1007/3-540-10001-6_21.
Piccinini, G., 2008. Computers. Pacific Philosophical Quarterly [Online], 89(1), pp.32–73. https://doi.org/10.1111/j.1468-0114.2008.00309.x.
Pierce, B.C. and Turner, D.N., 2000. Pict: a programming language based on the pi-calculus. Proof, Language and Interaction: Essays in Honour of Robin Milner. Cambridge, MA: MIT Press, pp.455–494.
Pour-El, M.B., 1999. The structure of computability in analysis and physical theory: an extension of Church’s thesis. In: E. Griffor, ed. Handbook of Computability Theory, Studies in Logic and the Foundations of Mathematics [Online]. Amsterdam: Elsevier, pp.449–471. https://doi.org/10.1016/S0049-237X(99)80029-9.
Prasse, M. and Rittgen, P., 1998. Why Church’s thesis still holds. some notes on Peter Wegner’s tracts on interaction and computability. The Computer Journal [Online], 41, pp.357–362. https://doi.org/10.1093/comjnl/41.6.357.
Rapaport, W.J., 2018. What is a computer? a survey. Minds and Machines [Online], 28(3), pp.385–426. https://doi.org/10.1007/s11023-018-9465-6.
Rogers, H., 1987. Theory of recursive functions and effective computability. Cambridge, MA: MIT Press. https://doi.org/10.2307/3614588.
Siegelmann, H.T., 1995. Computation beyond the Turing limit. Science [Online], 268(5210), pp.545–548. https://doi.org/10.1126/science.268.5210.545.
Smith, B.C., 2002. The foundations of computing. In: M. Scheutz, ed. Computationlism: new directions. Cambridge, MA: MIT Press.
Soare, R.I., 2013. Interactive computing and relativized computability. In: Computability: Turing, Godel, Church, and Beyond [Online]. Ed. by B.J. Copeland. Cambridge, MA: MIT Press. Chap. 9, pp.214–271. https://doi.org/10.7551/mitpress/8009.003.0010.
Staiger, L., 1997. Omega-languages. In: Handbook of formal languages [Online]. Ed. by G. Rozenberg and A. Salomaa. Berlin; Heidelberg: Springer, pp.339–387. https://doi.org/10.1007/978-3-642-59126-6_6.
Thomas, W., 1990. Automata on infinite objects. In: Formal models and semantics [Online]. Amsterdam: Elsevier. Chap. 4, pp.133–191. https://doi.org/10.1016/b978-0-444-88074-1.50009-3.
Turing, A., 1937. On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society [Online], s2-42(1), pp.230–265. https://doi.org/10.1112/plms/s2-42.1.230.
Van Leeuwen, J. and Wiedermann, J., 2000. On the power of interactive computing. In: J. van Leeuwen et al., eds. Theoretical computer science: exploring new frontiers of theoretical informatics [Online]. Vol. 1872, TCS 2000. Lecture Notes in Computer Science. Berlin; Heidelberg: Springer. https://doi.org/10.1007/3-540-44929-9_48.
Van Leeuwen, J. and Wiedermann, J., 2001. Beyond the turing limit: Evolving interactive systems. In: L. Pacholski and P. Ružička, eds. SOFSEM 2001: Theory and Practice of Informatics [Online]. Vol. 2234, Lecture notes in computer science. Berlin; Heidelberg: Springer, pp.90–109. https://doi.org/10.1007/3-540-45627-9_8.
Van Leeuwen, J. and Wiedermann, J., 2006. A theory of interactive computation. Interactive computation: the new paradigm [Online]. Berlin; Heidelberg: Springer, pp.119–142. https://doi.org/10.1007/3-540-34874-3_6.
Wegner, P., 1995. Interaction as a basis for empirical computer science. ACM Computing Surveys (CSUR) [Online], 27(1), pp.45–48. https://doi.org/10.1145/214037.214092.
Wegner, P., 1997. Why interaction is more powerful than algorithms. Communications of the ACM [Online], 40(5), pp.80–91. https://doi.org/10.1145/253769.253801.
Wegner, P., 1998. Interactive foundations of computing. Theoretical Computer Science [Online], 192(2), pp.315–351. https://doi.org/10.1016/S0304-3975(97)00154-0.
Wegner, P. and Goldin, D., 1999. Interaction as a framework for modeling. In: G. Goos et al., eds. Conceptual modeling: current issues and future directions [Online]. Vol. 1565, Lecture Notes in Computer Science. Berlin; Heidelberg: Springer, pp.243–257. https://doi.org/10.1007/3-540-48854-5_19.
Wegner, P. and Goldin, D., 2003. Computation beyond Turing machines. Communications of the ACM [Online], 46(4), pp.100–102. https://doi.org/10.1145/641205.641235.
Wegner, P. and Goldin, D., 2006. Principles of problem solving. Communications of the ACM [Online], 49(7), pp.27–29. https://doi.org/10.1145/1139922.1139942.