I was reading Paul Churchland's "Engine of Reason, Seat of the Soul", where argues that humans (and potentially artificial neural networks as well) are capable of non-Turing computation because they can find solutions to a problem by recognizing the pattern of the problem, instead of trying to algorithmically solve the problem.

He doesn't use the word Oracle Machine in his text anywhere, but that's what he seems to be describing: The human mind/neural net can, based on what it has learned, recognize the solution immediately (or at least much faster than a regular UTM), so it is effectively working as one of Turing's Oracle Machines, and allowing for non-Turing computation. This reasoning doesn't have to apply to just neural networks, it would be possible to pull off the same thing with any sufficiently powerful pattern recognition algorithm (a random forest, a support vector machine, etc...).

But I'm wondering if his reasoning is valid: Isn't that just shifting the computational effort somewhere else? The knowledge that went into the training of the pattern recognition system had to come from somewhere, and that is where the "normal" non-Oracle Turing computation occurred. Then is was just passed on to the PR method.

So my question is:

Do PR systems that function this way constitute Oracle Machines in the Turing sense of the word? Is Churchland's reasoning valid? Or is he wrong, and what the human mind and various PR algorithms pull off isn't "real" non-Turing computing?

  • 2
    $\begingroup$ I don't think this is a research level question. You can just use a single TM to sample a data set, train the neural net, and simulate it. No extra computational power is gained this way. $\endgroup$ Commented Jan 25, 2017 at 3:21

1 Answer 1


There is currently zero evidence contrary to the Church-Turing thesis -- namely that the Turing machine is the strongest physically realizable computational paradigm. In the case of AI systems, the claim is obviously wrong: these are implemented on regular computers, which are equivalent to Turing machines in computational power (or would be, if they had unbounded memory). In the case of human reasoning, one has some very dubious wiggle room by suggesting that neural computation might be exploiting some as of yet not understood physical process which enables it to decide non-Turing decidable problems. I don't know of any serious scientist (computer or otherwise) who takes that claim seriously.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.