Tesi di Church-Turing
Ipotesi: tutto ciò che è intuitivamente «effettivamente calcolabile» può essere calcolato da una macchina di Turing (o dal lambda calcolo, che è equivalente). Non è un teorema dimostrabile, ma una definizione di «calcolabile».
Formulata indipendentemente da Church e Turing nel 1936. Conseguenza: tutti i modelli di calcolo «ragionevoli» (macchine di Turing, lambda calcolo, macchine a registri, funzioni ricorsive, automi cellulari, il Gioco della vita di Conway) sono equivalenti. Estensione moderna: la tesi di Church-Turing forte, secondo cui tutte le funzioni effettivamente calcolabili sono equivalenti in tempo polinomiale. L'informatica quantistica mette in discussione la versione forte (l'algoritmo di Shor fattorizza in tempo polinomiale; i metodi classici no).