Church?Turing thesis

In computability theory the Church?Turing thesis, Church's thesis, Church's conjecture or Turing's thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers.

References

• Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
• Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
• Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
• Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
• Gödel, K., 1934, "On Undecidable Propositions of Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.
• Herbrand, J., 1932, "Sur la non-contradiction de l'arithmetique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
• Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
• Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
• Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14.
• Turing, A.M., 1936, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265.
• Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.
• Willem Fouché, Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442
• E. Bernstein, U. Vazirani, Quantum complexity theory, SIAM Journal on Computing 26(5) (1997) 1411?1473