Church-Turingthese
Hypothese dat alles wat intuïtief "effectief berekenbaar" is, door een turingmachine (of het equivalente lambdacalculus) berekend kan worden. Geen bewijsbare stelling, maar een definitie van "berekenbaar".
Church en Turing kwamen er onafhankelijk van elkaar op uit (1936). Gevolg: alle "redelijke" rekenmodellen (turingmachines, lambdacalculus, registermachines, recursieve functies, cellulaire automaten, Conway's Game of Life) zijn gelijkwaardig. Moderne uitbreiding: de sterke Church-Turingthese, die stelt dat alle effectief berekenbare functies polynomiaal equivalent zijn. Quantumcomputing zet die sterke variant onder druk: Shors algoritme ontbindt getallen in polynomiale tijd, klassieke methoden niet.