Sat 03:30 PM
CSCI 5100
The Church-Turing thesis concerns the concept of an effective or systematic or mechanical method, as used in logic, mathematics and computer science. “Effective” and its synonyms “systematic” and “mechanical” are terms of art in these disciplines: they do not carry their everyday meaning. A method, or procedure, M, for achieving some desired result is called “effective” (or “systematic” or “mechanical”) just in case:
We shall use the expression “computable function” to mean a function calculable by a machine, and let “effectively calculable” refer to the intuitive idea without particular identification with any one of these definitions.
No computational procedure will be considered as an algorithm unless it can be represented as a Turing Machine
It was stated … that “a function is effectively calculable if its values can be found by some purely mechanical process”. We may take this literally, understanding that by a purely mechanical process one which could be carried out by a machine. The development … leads to … an identification of computability with effective calculability.
Every effectively calculable function is a computable function
Λ:={λx.M∣x∈V,M∈Λ}∪{x∣x∈V}
B={akbkck|k∈N}
a, b, cx,yx and yM= “On input w
Hilbert[10], if fast