CONTRIBUTI / 1 / Simone Pinna, Marco Giunti /
The work of Alan Turing (1936) set a milestone for the foundation of the concept of algorithm by grounding the notion of effective procedure on a special type of real cognitive phenomenon, namely, that of a human being performing rule-based symbolic transformations with the only aid of paper and pencil. In this work, after a brief historical overview, we show how Turing arrived at a negative solution of the decidability problem for first-order logic and in which sense Turing’s explication of the intuitive concept of effective procedure is sufficient to justify Church’s Thesis. We then present a cognitive interpretation of Turing’s theory of computation, according to which Turing machines are viewed as models of real phenomena of mind-environment interaction.
References
Primary Sources
- Church, A. 1936. An unsolvable problem of elementary number theory, «Journal of Mathematics», 58, pp. 345-363.
- Giunti, M., Pinna, S. 2016. Toward a dynamical theory of human computation, «Logic Journal of IGPL», 24 (4), 557-569.
- Gödel, K. 1931. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I, «Monatshefte für Mathematik und Physik», 38, pp. 173-198.
- Gödel, K. 1934, On Undecidable Propositions of Formal Mathematical Systems, in Davis, M. (ed.) 1965. The Undecidable, Raven Press, Hewlett, New York, pp. 39-74.
- Turing, A. M. 1936. On computable numbers, with an application to the Entscheidungsproblem, «Proceedings of the London Mathematical Society» (pp. 230–265), London, Oxford Journals.
- Turing, A. M. 1950. Computing machinery and intelligence, «Mind», 236(59), pp. 433-460.
- Wells, A. 1998. Turing’s analysis of computation and theories of cognitive architecture, «Cognitive Science», 22, 269–294.
- Wells, A. 2005. Rethinking cognitive computation: Turing and the science of the mind, Palgrave McMillan, Basingstoke.
Secondary Literature
- Boolos, G. S., Burgess, J. P., Jeffrey, R. C. 2002. Computability and logic, Cambridge University Press, Cambridge, England.
- Dalla Chiara, M. L. 1974. La logica, Isedi, Milano.
- Longo, G. 2011. Reflections on Concrete Incompleteness, «Philosophia Mathematica», 19, 3, pp. 255–280.
- Newen A., De Bruin L., Gallagher S. (Eds.) 2018. The Oxford handbook of 4E cognition, Oxford University Press, New York (NY).
- Piccinini, G. 2009. Computationalism in the philosophy of mind, «Philosophy Compass», 4(3), pp. 515-532.
- Wilson, R. A. 1994. Wide computationalism, «Mind», 103(411), pp. 351-372.