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

[Martin Davis]

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>