Church-Turing-tesen
Church-Turing-tesen er indenfor beregnelighedsteori en hypotese om computeres opførsel. Tesen påstår, at enhver mulig udregning kan udføres af en algoritme på en computer, givet at der er tilstrækkelig megen tid og lagerplads til rådighed. Tesen kan ikke bevises matematisk; den bliver nogle gange brugt som en definition.
Uformelt siger tesen, at vores opfattelse af "algoritme" kan præciseres, og derved kan algoritmer køres på computere. En computer kan i teorien køre enhver algoritme; hvilket vil sige, at alle almindelige computere er ækvivalente med hensyn til teoretisk beregningskraft (computational power), og det er derfor ikke muligt at konstruere en beregningsenhed, som er mere kraftfuld end den simpleste computer (Turingmaskinen). Det skal nævnes at formuleringen omkring kraft ser bort fra praktiske faktorer som hastighed og hukommelse; den tager højde for alt, som er teoretisk muligt, givet ubegrænset tid og hukommelse.
Tesen blev først fremført af Stephen Kleene i 1943, men opkaldt efter Alonzo Church og Alan Turing.
Formel fremstilling
Tesen kan fremstilles således:
- "Enhver 'funktion som naturligt ville blive betragtet som beregnelig' kan beregnes af en Turingmaskine."
Med baggrund i det svagt formulerede koncept "funktion som naturligt ville blive betragtet som beregnelig", kan tesen ikke formelt blive bevist. Et modbevis vil kun være muligt, hvis man kunne konstruere hypercomputere, hvis resultater "naturligt skulle betragtes som beregnelige".
Ethvert ikke-interaktivt computerprogram kan blive oversat til en Turingmaskine, og enhver Turingmaskine kan oversættes til ethvert Turing-fuldstændigt programmeringssprog, så tesen er ækvivalent med at sige, at ethvert Turing-fuldstændigt programmeringssprog er tilstrækkeligt til at udtrykke enhver algoritme.
Der eksisterer variationer af tesen; f.eks. siger den fysiske Church–Turing-tese:
- "Enhver funktion som fysisk kan blive beregnet, kan beregnes af en Turingmaskine."
En anden variation er den stærke Church–Turing-tese (strong Church–Turing thesis), som ikke oprinder fra Church's eller Turings arbejde, men snarere løbende i takt med udviklingen af kompleksitetsteori. Den siger:
- "Enhver 'rimelig' beregnelighedsmodel kan effektivt simuleres på en probabilistisk Turingmachine."
Ordet 'effektivt' betyder her op til polynomialtidsreduktioner. Den stærke Church-Turing-tese postulerer da, at alle 'rimelige' beregnelighedsmodeller udtrykker den samme klasse af problemer, som kan beregnes i polynomiel tid. Forudsat formodningen at probabilistisk polynomiel tid (BPP) er lig deterministisk polynomiel tid (P), er ordet 'probabilistisk' valgfrit i den stærke Church-Turing-tese.
Hvis kvanteberegning var fysisk muligt, ville kvantecomputere modbevise den stærke Church-Turing-tese, da det forudsættes, at kvantum polynomiel tid (BQP) er større end BPP. Sagt på en anden måde, der er effektive kvantealgoritmer, som kan udføre opgaver, hvortil der ikke kendes til effektive probabilistiske algoritmer; eksempelvis faktorering af heltal.
Historie
En præcis definition af begrebet algoritme kom først i 1936. Alonzo Church gjorde det med -kalkylen og Alan Turing med sin Turingmaskine. Modellerne har senere vist sig at være ækvivalente. Forbindelsen mellem en beskrivende betegnelse og en præcis definition af en algoritme kendes i dag som Church-Turing-tesen.
 | Wikimedia Commons har medier relateret til: |
|