The Church-Turing Thesis states that a computational method can only be considered effective if a Turing machine can complete it.
– The method terminates (finishes) after a finite number of steps. – The method always produces a correct answer. – In principle, the solution must be achievable using nothing but writing materials. (This does not have to carry into practice).Description
The history of the Church-Turing thesis takes us back to the 1930s. Then, when the most critical issue in theoretical mathematics was the potential introduction of a mechanical way of separating mathematical truths from mathematical falsehoods.
– The 10th Problem by Hilbert – Are All Algorithms Able to Be Completed by a Turing Machine? – Turing Conversion