Is the church turing thesis a red herring for cognitive science?

PETTERS, Dean and JUNG, A. (2021). Is the church turing thesis a red herring for cognitive science? In: AISB Convention 2021. Society for the Study of Artificial Intelligence and Simulation of Behaviour, 162-165.

PettersJung_CTT_RedHerring_AISB2021.pdf - Accepted Version
All rights reserved.

Download (262kB) | Preview
Official URL:


This paper considers whether computational formalisms beyond the Church Turing Thesis (CTT) could be helpful in understanding the mind. We argue that they may be, and that the way that the CTT has been invoked in Cognitive Science may therefore act as a Red Herring. That is, the way the CTT is invoked in Cognitive Science may mislead and perhaps contribute to premature abandonment of possibly fruitful research directions in Cognitive Science. We do not suggest some sort of “hypercomputation’. Whilst it is possible to use a rich interactive machine to implement a simple function this does not lead to new computable functions. In other words, the CTT is valid even if more sophisticated machinery is employed. It is the other direction that is the core of this paper: When considering more sophisticated computational tasks, then standard Turing machines (and their mode of operation) are not sufficient to explore the range of possibilities. The CTT is commonly interpreted as stating that the intuitive concept of computability is fully captured by Turing machines or any equivalent formalism (such as recursive functions, the lamba calculus, Post production rules, and many others). The CTT implies that if a function is (intuitively) computable, then it can be computed by a Turing machine. Conversely, if a Turing machine cannot compute a function, it is not computable by any mechanism whatsoever. We suggest an inadvertent error that has been made which is the claim that relatively simple computational formalisms like Turing Machines can do anything that more complex computional formalisms can do. To show this we present the landscape of computability within and beyond the bounds covered by the mathematical CTT. This shows that in regions of the computational landscape beyond the CTT there may be hierarchies of increasingly powerful computational formalisms. Erroneously interpreting CTT as enforcing a ‘one size fits all’ interpretation to computational formalisms leads to extreme reductionism that means contemporary computationalism is viewed as inadequate to explaining many phenomena related to thought and mind in living systems. Once this Red Herring interpretation for CTT is avoided this leaves the way open to exploring how richer kinds of computation that may possess many shades of expressivity can form part of Cognitive Science explanations.

Item Type: Book Section
Page Range: 162-165
SWORD Depositor: Symplectic Elements
Depositing User: Symplectic Elements
Date Deposited: 28 Jul 2021 10:14
Last Modified: 17 Aug 2021 15:11

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics