[FOM] "algorithm" and the Church-Turing Thesis
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
BTW the word "algorithm" occurs in none of the key founding papers by
Church, Turing, Post, Kleene.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the FOM