[FOM] "algorithm" and the Church-Turing Thesis

Martin Davis martin at eipye.com
Mon Aug 22 14:57:57 EDT 2016


The ongoing discussion on "Counterfactuals in relative computability
theory" seems to take as a given that the Church-Turing Thesis makes
precise the notion of "algorithm". But the Church-Turing Thesis says
nothing about what algorithms ARE. It is about what algorithms can and can
not DO. So for a given set S of natural numbers, the Church-Turing Thesis
asserts that there is an algorithmic method for determining of a given
natural number whether or not it belongs to S if and only if S is Turing
computable.

BTW the word "algorithm" occurs in none of the key founding papers by
Church, Turing, Post, Kleene.

Martin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160822/d5972b05/attachment.html>


More information about the FOM mailing list