Church-Turings hypotes
Inom matematik och beräkningsteori innebär Church-Turings hypotes påståendet att en matematisk funktion är effektivt beräkningsbar om och endast om den kan beräknas med hjälp av en algoritm på en Turingmaskin, d.v.s. om beräkningarna kan utföras med någon annan godtycklig manuell eller mekanisk metod, så kan de också utföras av en sådan maskin. Tesen formulerades först av Stephen Kleene 1943 men är uppkallad efter Alonzo Church och Alan Turing.
Flera försök gjordes under 1920- och 30-talen för att formalisera begreppet beräkningsbarhet:
- Amerikanske matematikern Alonzo Church skapade en metod för att definiera funktioner s.k. lambdakalkyl (
λ -kalkyl), - Brittiske matematikern Alan Turing skapade en teoretisk modell för en maskin, som nu kallas en universell Turingmaskin som kunde utföra beräkningar utifrån olika indata,
- Church skapade tillsammans med matematikern Stephen Kleene och logikern John Barkley Rosser en formell definition av en klass av funktioner vars värden kan beräknas genom rekursion.
Alla tre beräkningsprocesserna (rekursion,
Church-Turing hypotesen har numera en mycket spridd acceptans, men trots detta är den grundläggande premissen bakom hypotesen - idén om vad det innebär för en funktion för att vara effektivt beräkningsbar - något vag och intuitiv, och hypotesen kan därför inte formellt bevisas utan förblir en hypotes[3].