×

Computation as social agency: what, how and who. (English) Zbl 1395.68119

Summary: Computation today is interactive agency in social networks. In this discussion paper, we look at this trend through the lens of logic, identifying two main lines. One is ‘epistemization’, making computational tasks refer explicitly to knowledge or beliefs of the agents performing them. The other line is using games as a model for computation, leading to ‘gamification’ of classical tasks, and computing by agents that may have preferences. This provides ingredients for a fundamental theory of computation that shifts from what is computed to how it is computed and by whom, moving from output to social behavior. The true impact of this shift is not in learning how to replace humans, but in creating new societies where humans and machines interact. While we do not offer a Turing-style account of this richer world, we discuss what becomes of three classical themes: the Universal Machine, Church’s Thesis and the Turing Test.

MSC:

68Q01 General topics in the theory of computing
03B42 Logics of knowledge and belief (including belief change)
68T27 Logic in artificial intelligence
91A80 Applications of game theory
91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abramsky, Samson, Information, processes, and games, (Adriaans, Pieter; van Benthem, Johan, Handbook of the Philosophy of Information, (2008), Elsevier Science Amsterdam), 483-549 · Zbl 1143.68468
[2] Samson Abramsky, Tutorial on game semantics, LINT Workshop University of Amsterdam, Department of Computing Oxford University, 2008.; Samson Abramsky, Tutorial on game semantics, LINT Workshop University of Amsterdam, Department of Computing Oxford University, 2008. · Zbl 1097.68574
[3] Samson Abramsky, Foundations of interactive computation, Invited Lecture, ASL Colloquium Alan Turing Year, University of Manchester, 2012.; Samson Abramsky, Foundations of interactive computation, Invited Lecture, ASL Colloquium Alan Turing Year, University of Manchester, 2012.
[4] Ågotnes, Thomas; van Ditmarsch, Hans, What will they say? public announcement games, Synthese, 179, 1, 57-85, (2011) · Zbl 1222.03021
[5] Aucher, Guillaume; van Benthem, Johan; Grossi, Davide, Sabotage modal logic: some model- and some proof-theoretic aspects, J. Log. Comput., (2016), in press · Zbl 1471.03040
[6] Axelrod, Robert, The evolution of cooperation, (1984), Basic Books New York · Zbl 1225.92037
[7] Baltag, Alexandru; Moss, Lawrence; Solecki, Slawomir, The logic of public announcements, common knowledge, and private suspicions, (Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge, (1998), Morgan Kaufmann Publishers San Francisco), 43-56 · Zbl 1386.03019
[8] Baltag, Alexandru; Smets, Sonja, A qualitative theory of dynamic interactive belief revision, (Bonanno, Giacomo; van der Hoek, Wiebe; Wooldridge, Michael, Logic and the Foundations of Game and Decision Theory, (2008), Amsterdam University Press Amsterdam), 13-60 · Zbl 1261.03077
[9] (Bergstra, Jan; Ponse, Alban; Smolka, Scott, Handbook of Process Algebra, (2001), Elsevier Science Amsterdam)
[10] Blackburn, Patrick; de Rijke, Maarten; Venema, Yde, Modal logic, (2000), Cambridge University Press Cambridge, UK · Zbl 0988.03006
[11] Bolander, Thomas; Andersen, Mikael, Epistemic planning for single- and multi-agent systems, J. Appl. Non-Class. Log., 21, 1, 9-34, (2011) · Zbl 1242.68285
[12] Brafman, Ronen; Latombe, Jean-Claude; Shoham, Yoav, Towards knowledge-level analysis of motion planning, (Proceedings AAAI-93, (1993)), 670-675
[13] Brandenburger, Adam, The language of game theory: putting epistemics into the mathematics of games, (2014), World Scientific Singapore · Zbl 1298.91021
[14] Büchi, Richard; Landweber, Lawrence, Definability in the monadic second-order theory of successor, J. Symb. Log., 34, 2, 166-170, (1969) · Zbl 0209.02203
[15] Christoff, Zoé, Dynamic logics of networks: information flow and the spread of opinion, (2016), Institute for Logic, Language and Computation Amsterdam, Dissertation
[16] Cogan, Eva; Parikh, Rohit; Pacuit, Eric, The logic of knowledge-based obligation, Synthese, 149, 2, 311-341, (2006) · Zbl 1103.03009
[17] Cohen, Philip R.; Levesque, Hector, Intention is choice plus commitment, Artif. Intell., 42, 3, 213-261, (1990) · Zbl 0721.03017
[18] Cooper, Barry, Computability theory, (van Benthem, J.; Gupta, A., Logic and Philosophy Today, vol. 1, (2011), College Publications London), 197-218 · Zbl 1273.03139
[19] (Cooper, Barry; Löwe, Benedikt; Sorbi, Andrea, New Computational Paradigms. Changing Conceptions of What is Computable, (2001), Springer Science Publishers New York) · Zbl 1130.68005
[20] Dijkstra, Edsger, Go to statement considered harmful, Commun. ACM, 11, 147-148, (1968)
[21] Dung, Phan Minh, On the acceptability of arguments and its fundamental role in non-monotonic reasoning, Artif. Intell., 77, 2, 321-358, (1995) · Zbl 1013.68556
[22] (Ulle, Endriss; Lang, Jerome, Proceedings of the First International Conference on Computational Social Choice, (2006), ILLC, University of Amsterdam)
[23] Fagin, Ronald; Halpern, Joseph; Moses, Yoram; Vardi, Moshe, Reasoning about knowledge, (1996), The MIT Press Cambridge, MA · Zbl 0839.68095
[24] Fiutek, Virginie, Playing with knowledge and belief, (2013), University of Amsterdam, PhD thesis, ILLC Dissertation DS-2013-02
[25] Gabbay, Dov; Grossi, Davide, When are two arguments the same?, (Baltag, Alexandru; Smets, Sonja, Johan van Benthem on Logic and Information Dynamics, (2015), Springer Publishers Dordrecht), 677-701 · Zbl 1335.03004
[26] (Gabbay, Dov; Guenthner, Franz, Handbook of Philosophical Logic, (1981), Kluwer Publishers Dordrecht) · Zbl 1259.03001
[27] (Gabbay, Dov; Horty, John; van der Meyden, Ron; Parent, Xavier; van der Torre, Leon, Handbook of Logic and Normative Systems, (2013), College Publications London)
[28] (Gabbay, Dov; Maibaum, Tom; Shepherdson, John, Handbook of Logic in Artificial Intelligence and Logic Programming, (1995), Oxford University Press Oxford)
[29] (Ghosh, Sujata; van Benthem, Johan; Verbrugge, Rineke, Models of Strategic Reasoning: Logics, Games, and Communities, FoLLI Lecture Notes, (2016), Springer Science Heidelberg) · Zbl 1327.91003
[30] Gierasimczuk, Nina, Knowing One’s limits, logical analysis of inductive inference, (2011), ILLC, University of Amsterdam, Dissertation DS-2010-11
[31] (Gigerenzer, Gerd; Todd, Peter; the ABC Research Group, Simple Heuristics That Make Us Smart, (1999), Oxford University Press Oxford)
[32] Girard, Patrick; Liu, Fenrong; Seligman, Jeremy, Logical dynamics of belief change in the community, Synthese, 191, 11, 2402-2431, (2014) · Zbl 1317.03010
[33] (Graedel, Erich; Thomas, Wolfgang; Wilke, Thomas, Automata, Logics, and Infinite Games, (2002), Springer Science Heidelberg) · Zbl 1011.00037
[34] Grossi, Davide, Argumentation theory in the view of modal logic, (McBurney, Peter; Rahwan, Iyad, Post-Proceedings of the Seventh International Workshop on Argumentation in Multi-Agent Systems, Lecture Notes in AI, vol. 6614, (2011), Springer Publishers Heidelberg), 190-208
[35] Grossi, Davide; Turrini, Paolo, Short-sight in extensive games, (Conitzer, Vincent; Winikoff, Michael, Proceedings AAMAS 11, (2012)), 805-812
[36] Gutierrez, Julian; Harrenstein, Paul; Wooldridge, Michael, Iterated Boolean games, Inf. Comput., 242, 53-79, (2015) · Zbl 1318.91012
[37] Halpern, Joseph; Vardi, Moshe, The complexity of reasoning about knowledge and time, I. lower bounds, J. Comput. Syst. Sci., 38, 1, 195-237, (1989) · Zbl 0672.03015
[38] Harel, David, Can programming be liberated, period?, IEEE Comput. Soc., 41, 1, 28-37, (2008)
[39] Harel, David; Kozen, Dexter; Tiuryn, Jerzy, Dynamic logic, (2000), The MIT Press Cambridge, MA · Zbl 0976.68108
[40] Harel, David; Kugler, Hillel; Marelly, Rami; Pnueli, Amir, Smart play-out of behavioral requirements, (Aagaard, Mark; O’Leary, John, Formal Methods in Computer-Aided Design, LNCS, vol. 2517, (2002), Springer Publishers Heidelberg), 378-396 · Zbl 1019.68622
[41] Hendricks, Vincent; Hansen, Pelle, Infostorms, (2014), Copernicus Books and Springer Publishers New York
[42] Hintikka, Jaakko; Sandu, Gabriel, Game-theoretical semantics, (van Benthem, Johan; ter Meulen, Alice, Handbook of Logic and Language, (1997), Elsevier Science Publishers Amsterdam), 361-410
[43] Hofbauer, Josef; Sigmund, Karl, Evolutionary games and population dynamics, (1998), Cambridge University Press Cambridge, UK · Zbl 0914.90287
[44] Holiday, Wesley, Knowing what follows: epistemic closure and epistemic logic, (2014), Department of Philosophy, Stanford University, ILLC Dissertation Series DS-2012-09
[45] Isaac, Alistair; Szymanik, Jakub; Verbrugge, Rineke, Logic and complexity in cognitive science, (Baltag, Alexandru; Smets, Sonja, Johan van Benthem on Logic and Information Dynamics, (2015), Springer Publishers Dordrecht), 787-833 · Zbl 1319.91136
[46] Jones, Neil, Blindfold games are Harder than games with perfect information, Bull. Eur. Assoc. Theor. Comput. Sci., 6, 4-7, (1978)
[47] Kamlah, Wilhelm; Lorenzen, Paul, Logische propädeutik, (1967), Bibliographisches Institut Mannheim
[48] Kelly, Kevin, The logic of reliable inquiry, (1996), Oxford University Press Oxford · Zbl 0910.03023
[49] (Law, Edith; von Ahn, Luis, Human Computation, (2011), Margan Claypool Publishers San Rafael)
[50] Lehrer, Keith, Theory of knowledge, (1990), Westview Press Boulder, CO · Zbl 0952.03508
[51] Leyton-Brown, Kevin; Shoham, Yoav, Multiagent systems: algorithmic, game theoretic and logical foundations, (2009), Cambridge University Press Cambridge, UK · Zbl 1163.91006
[52] Liu, Fenrong, Dynamic logic of preference change, (2011), Springer Publishers Dordrecht · Zbl 1230.03003
[53] Löding, Christof; Rohde, Philipp, Model checking and satisfiability for sabotage modal logic, (Pandya, Paritosh; Ramakrishnan, Jaikumar, Proceedings FSTTCS 2003, Lecture Notes in Computer Science, vol. 2914, (2003), Springer Verlag Heidelberg), 302-313 · Zbl 1205.68222
[54] Loewe, Benedikt; Pacuit, Eric; Witzel, Andreas, Del planning and some tractable cases, (van Ditmarsch, Hans; Lang, Jerome; Ju, Shier, Proceedings LORI Guangzhou, (2011), Springer Science Heidelberg), 179-192 · Zbl 1298.03054
[55] Meijering, Ben; Taatgen, Niels; van Rijn, Hedderik; Verbrugge, Rineke, What eye movements can tell about theory of mind in a strategic game, PLoS ONE, 7, 9, (2012)
[56] Miller, Joseph; Moss, Lawrence, The undecidability of iterated relativization, Stud. Log., 97, 373-407, (2005) · Zbl 1088.03016
[57] Minica, Stefan, Dynamic logic of questions, (2011), University of Amsterdam, PhD thesis, ILLC Dissertation DS-2011-08 · Zbl 1196.03027
[58] Moore, Robert, A formal theory of knowledge and action, (1984), Artificial Intelligence Center, SRI International Menlo Park, Technical Report
[59] Moses, Yoram, Realting knowledge and coordinated action: the knowledge of preconditions principle, (Proceedings TARK, CMU Pittsburgh, (2015))
[60] Nozick, Robert, Philosophical explanations, (1981), Harvard University Press Cambridge, MA
[61] Osborne, Michael; Rubinstein, Ariel, A course in game theory, (1994), The MIT Press Cambridge, MA · Zbl 1194.91003
[62] Pacuit, Eric; Roy, Olivier, Interactive rationality, Lecture Notes, (2015), Department of Philosophy, University of Maryland and Institute for Philosophy, University of Bayreuth · Zbl 1298.91048
[63] Papadimitriou, Christos, Computational complexity, (1994), Addison-Wesley Reading · Zbl 0833.68049
[64] Parikh, Rohit, Social software, Synthese, 132, 187-211, (2002) · Zbl 1036.91048
[65] Parikh, Rohit; Ramanujam, Ramaswamy, A knowledge-based semantics of messages, J. Log. Lang. Inf., 12, 4, 453-467, (2003) · Zbl 1031.03021
[66] Perea, Andres, Epistemic game theory, (2012), Cambridge University Press Cambridge, UK · Zbl 1294.91029
[67] Reiter, Raymond, Knowledge in action, (2001), The MIT Press Cambridge, MA · Zbl 1018.03022
[68] Rohde, Philipp, On games and logics over dynamically changing structures, (2005), Department of Informatics, Rheinisch-Westfälische Technische Hochschule Aaachen, PhD thesis
[69] Searle, John; Vanderveken, Daniel, Foundations of illocutionary logic, (1985), Cambridge University Press Cambridge, UK · Zbl 0577.03011
[70] Sergot, Marek, Temporal logic of events and preference, (2008), Department of Computing, Imperial College London
[71] Sevenster, Merlijn, Branches of imperfect information: logic, games and computation, (2006), ILLC, University of Amsterdam, Dissertation DS-2006-06 · Zbl 1169.68439
[72] Shi, Chenwei; Smets, Sonja, Beliefs supported by arguments, (Proceedings Chinese Conference on Logic and Argumentation, CLAR 2016, Hangzhou, CEUR Proceedings Collection, (2016))
[73] Shoham, Yoav, Agient-oriented programming, Artif. Intell., 60, 1, 51-92, (1993)
[74] Skyrms, Brian, The dynamics of rational deliberation, (1990), Harvard University Press Cambridge, MA · Zbl 0797.90002
[75] Stanley, Jason, Know how, (2011), Oxford University Press Oxford
[76] Stanley, Jason; Williamson, Timothy, Knowing how, J. Philos., 98, 8, 411-444, (2001)
[77] Su, Kaile; Sattar, Abdul; Governatori, Guido; Chen, Qingliang, A computationally grounded logic of knowledge, belief and certainty, (Proceedings AAMAS ’05, (2005)), 149-156
[78] Turing, Alan, On computable numbers, with an application to the entscheidungsproblem, Proc. Lond. Math. Soc., 2, 42, 230-265, (1937) · Zbl 0016.09701
[79] van Benthem, Johan, Computation as conversation, (Löwe, B.; etal., New Computational Paradigms, (2008), Springer Science Publishers New York), 35-58 · Zbl 1145.03016
[80] van Benthem, Johan, Logical dynamics of information and interaction, (2011), Cambridge University Press Cambridhe, UK · Zbl 1251.03003
[81] van Benthem, Johan, Logic in games, (2014), The MIT Press Cambridge, MA · Zbl 1291.03003
[82] van Benthem, Johan, Exploring logical dynamics, FoLLI Studies in Logic, Language and Information, (1996), CSLI Publications Stanford · Zbl 0873.03001
[83] van Benthem, Johan, An essay on sabotage and obstruction, (Hutter, Dietrich; Stephan, Werner, Mechanizing Mathematical Reasoning, Lecture Notes in Artificial Intelligence, vol. 2605, (2005), Springer Verlag) · Zbl 1098.68632
[84] van Benthem, Johan, Rational dynamics and epistemic logic in games, Int. Game Theory Rev., 9, 2, 377-409, (2007) · Zbl 1139.91313
[85] van Benthem, Johan, Oscillations, logic, and dynamical systems, (Ghosh, Sujata; Szymanik, Jakub, The Facts Matter, (2015), College Publications London), 9-22
[86] van Benthem, Johan; Bezhanishvili, Nick; Enqvist, Sebastian, A new game equivalence and its modal logic, (Proceedings TARK 2017, Liverpool, (2017)) · Zbl 1495.03052
[87] van Benthem, Johan; Gerbrandy, Jelle; Hoshi, Tomohiro; Pacuit, Eric, Merging frameworks for interaction, J. Philos. Log., 38, 491-526, (2009) · Zbl 1185.03019
[88] van Benthem, Johan; Martinez, Maricarmen, The stories of logic and information, (Adriaans, Pieter; van Benthem, Johan, Handbook of the Philosophy of Information, (2008), Elsevier Science Publishers Amsterdam), 217-280
[89] van Benthem, Johan; Pacuit, Eric, The tree of knowledge in action, (Proceedings Advances in Modal Logic, Melbourne, (2006)), 87-106 · Zbl 1148.03009
[90] van Benthem, Johan; Pacuit, Eric, Dynamic logic of evidence-based beliefs, Stud. Log., 99, 1, 61-92, (2011) · Zbl 1241.03013
[91] van Benthem, Johan; van Eijck, Jan; Kooi, Barteld, Logics of communication and change, Inf. Comput., 204, 1620-1662, (2006) · Zbl 1120.03012
[92] van der Hoek, Wiebe; Wooldridge, Michael, Tractable multiagent planning for epistemic goals, (Proceedings AAMAS ’02, (2002), ACM New York), 1167-1174
[93] van der Meyden, Ron, The dynamic logic of permission, J. Log. Comput., 6, 465-479, (1996) · Zbl 0855.03008
[94] van Ditmarsch, Hans, The Russian card problem: a case study in cryptography with public announcements, (Proceedings AWCL 2002, Canberra, (2002)), 47-67
[95] van Ditmarsch, Hans; van der Hoek, Wiebe; Kooi, Barteld, Dynamic epistemic logic, (2007), Springer Publishers Dordrecht · Zbl 1156.03015
[96] van Emde Boas, Peter, Machine models and simulations, (van Leeuwen, Jan, Handbook of Theoretical Computer Science, volume A (Algorithms and Complexity), (1990), North-Holland Amsterdam), 3-66 · Zbl 0900.68265
[97] Blokpoel, Mark; van Kesteren, Marlieke; Stolk, Arjen; Haselager, Pim; Toni, Ivan; van Rooij, Iris, Recipient design in communication: simple heuristics or perspective taking?, Front. Human Neurosci., 6, 253, 1-13, (2012)
[98] Hanna van Lee, Rasmus Rendsvig, Suzanne van Wijk, Merging frameworks for information dynamics: del, dynamical systems and etl, Center for Information and Bubble Studies, University of Copenhagen, and Lund University.; Hanna van Lee, Rasmus Rendsvig, Suzanne van Wijk, Merging frameworks for information dynamics: del, dynamical systems and etl, Center for Information and Bubble Studies, University of Copenhagen, and Lund University.
[99] Venema, Yde, Algebras and coalgebras, (Blackburn, Patrick; van Benthem, Johan; Wolter, Frank, Handbook of Modal Logic, (2006), Elsevier Science Amsterdam), 331-426 · Zbl 1110.68066
[100] Venema, Yde, Lectures on the modal mu-calculus, Lecture Notes, (2012), ILLC, University of Amsterdam · Zbl 1284.03153
[101] (Walz, Steffen; Deterding, Sebastian, The Gameful World: Approaches, Issues, Applications, (2015), The MIT Press Cambridge, MA)
[102] Wang, Yanjing, A logic of knowing how, (van der Hoek, Wiebe; Holliday, Wesley; Wang, Wan feng, Proceedings LORI Taipei, (2015)), 392-405 · Zbl 1471.03038
[103] Wellman, Michael, A market-oriented programming environment and its application to distributed multicommodity flow problems, J. Artif. Intell. Res., 1, 1-23, (1993) · Zbl 0900.90089
[104] Wooldridge, Michael, An introduction to multi-agent systems, (2009), John Wiley Sons New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.