Teza Churcha-Turinga
Hipoteza: wszystko, co intuicyjnie „efektywnie obliczalne”, da się obliczyć na maszynie Turinga (lub w równoważnym rachunku lambda). Nie twierdzenie do udowodnienia, lecz definicja „obliczalności”.
Church i Turing sformułowali ją niezależnie w 1936 roku. Konsekwencja: wszystkie „rozsądne” modele obliczeń (maszyny Turinga, rachunek lambda, maszyny rejestrowe, funkcje rekurencyjne, automaty komórkowe, Gra w życie Conwaya) są równoważne. Współczesne rozszerzenie, mocna teza Churcha-Turinga, mówi o równoważności wielomianowej. Komputery kwantowe podważają jej mocną wersję (algorytm Shora faktoryzuje w czasie wielomianowym, metody klasyczne nie).