Modelling interactive computing systems: Do we have a good theory of what computers are?

Main Article Content

Alice Martin
https://orcid.org/0000-0002-9023-506X
Mathieu Magnaudet
https://orcid.org/0000-0002-7548-6274
Stéphane Conversy
https://orcid.org/0000-0002-5145-6476

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

How to Cite
Martin, A., Magnaudet, M., & Conversy, S. (2022). Modelling interactive computing systems: Do we have a good theory of what computers are?. Philosophical Problems in Science (Zagadnienia Filozoficzne W Nauce), (73), 77–119. Retrieved from https://www.zfn.edu.pl/index.php/zfn/article/view/597
Section
Articles

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