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.