Church-Turing-tesen
Hypotes: allt som intuitivt är "effektivt beräkningsbart" kan beräknas av en Turing-maskin (eller lambda-kalkyl, som är ekvivalent). Inte ett bevisbart teorem — definition av "beräkningsbart".
Church + Turing oberoende av varandra (1936). Konsekvens: alla "rimliga" beräkningsmodeller (Turing-maskiner, lambda-kalkyl, register-maskiner, rekursiva funktioner, cellular automata, Conway's Life) är ekvivalenta. Modern utvidgning: Strong Church-Turing-tesen — alla effektivt beräkningsbara funktioner är polynomially-time-ekvivalenta. Quantum computing utmanar Strong-versionen (Shor's algoritm faktoriserar i polynomtid, klassiska metoder kan inte).