Computation as Social Agency: What and How
Johan van Benthem
Abstract:
We survey the history of computation since Turing, emphasizing the difference between the `what question' as to what can be computed and the `how question' of what behavior can be produced. We then look at social agency as a model for interactive computation, and investigate systematic ways of 'epistemizing' and 'gamifying' classical algorithmic tasks. This does not extend the realm of what can be computed, but it does extend the ways how we can compute, getting closer to the realities of modern hybrid computing systems of humans and machines, such as the Internet and its users. We also discuss what these developments mean for a modern understanding of the great foundational questions about computing: the search for a Universal Machine, Church's Thesis, and the Turing Test.
Note: This is a light paper behind a series of talks given on this subject at Stanford, the ASL Logic Colloquium in Manchester, the ESSLLI Summer School in Opole, Amsterdam, and JAIST (Kanazawa, Japan), and the Strachey Lecture given at Oxford 2015. It will appear in "Information and Computation", 2016.