1 COMPUTATION AS SOCIAL AGENCY: WHAT AND HOW 1

This Turing Year has been the occasion for lively debates about the nature of computing. Are we on the threshold of new styles of computation that transcend the limitations of the established paradigm? Let us briefly recall three classical themes of the golden age when Turing and his generation made computation a subject for mathematical inquiry, and hand in hand with that, for practical development. First of all, by analyzing the bare basics of mechanical computing, Turing defined a Universal Machine that can compute the result of any algorithm on any matching input, when both are presented in suitably encoded form. This notion then supported the subsequent development of Recursion Theory, bringing to light both the basic structures and powers of effective computation, but also its limitations as exemplified in the undecidability of the Halting Problem. On the basis of this and other, equivalent models proposed at the time, Church Thesis then claimed that all effectively computable functions over the natural numbers (a canonical domain that can mimic non-numerical computation by various encodings going back to Gödel and others), coincide with the ‘recursive functions’, that can be computed on Turing machines. As the power of this paradigm became clear, it was suggested in the famous Turing Test that computatio