Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why?Turing, Rosser etc used different terms todifferentiate between: what can be computed and what can becomputed by a Turing machine.Turing's 1939 definition regarding this is:We shall use the expression computable function to mean a functioncalculable by a machine, and we let effectively calculable refer tothe intuitive idea without particular identification with any one ofthese definitions.So, the Church-Turing thesis can be stated as follows:Every effectively calculable function is a computable function.So again, how will the proof look like if one disproves this conjecture?
What would it mean to disprove Church-Turing thesis?
computability;proofs;hypercomputation
The Church-Turing thesis has been proved for all practical purposes.http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402Dershowitz and Gurevich, Bulletin of Symbolic Logic, 2008.(This reference discusses the history of Church's and Turing's work, and argues for a separation between Church's Thesis and Turing's Thesis as distinct logical claims, then proves them both, within an intuitive axiomatization of computability.)