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.
Alan Turing and the Cognitive Foundation of the Concept of Algorithm
Simone Pinna
;Marco Giunti
2022-01-01
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
2022-34-Pinna-Giunti.pdf
accesso aperto
Tipologia:
versione editoriale
Dimensione
197.94 kB
Formato
Adobe PDF
|
197.94 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.