The Church-Turing-afhandlingen henviser til konceptet om en effektiv, systematisk eller mekanisk metode inden for logik, matematik og datalogi. Den er formuleret som en beskrivelse af det intuitive regneevnebegreb og kaldes i forhold til generelle rekursive funktioner oftere for Kirkens tese. Det refererer også til teorien om computer-beregnbare funktioner. Specialet udkom i 1930'erne, hvor selve computerne endnu ikke eksisterede. Det blev senere opkaldt efter den amerikanske matematiker Alonso Church og hans britiske kollega Alan Turing.
Effektivitet af metoden til at opnå resultatet
Den første enhed, der lignede en moderne computer, var Bombie, en maskine skabt af den engelske matematiker Alan Turing. Det blev brugt til at tyde tyske beskeder under Anden Verdenskrig. Men til sin afhandling og formalisering af begrebet en algoritme brugte han abstrakte maskiner, senere kaldet Turing-maskiner. Speciale præsentererinteresse for både matematikere og programmører, da denne idé inspirerede skaberne af de første computere.
I beregningsbarhedsteori er Church-Turing-afhandlingen også kendt som formodningen om karakteren af beregnelige funktioner. Den siger, at for enhver algoritmisk beregnelig funktion på naturlige tal er der en Turing-maskine, der er i stand til at beregne den. Eller med andre ord, der er en algoritme, der passer til det. Et velkendt eksempel på effektiviteten af denne metode er sandhedstabeltesten til test af tautologi.
En måde at opnå et ønsket resultat på kaldes "effektiv", "systematisk" eller "mekanisk", hvis:
- Metoden er specificeret i form af et endeligt antal nøjagtige instruktioner, hver instruktion er udtrykt ved hjælp af et endeligt antal tegn.
- Det vil køre uden fejl, vil give det ønskede resultat i et bestemt antal trin.
- Metoden kan udføres af et menneske uden hjælp med andet udstyr end papir og blyant
- Det kræver ikke forståelse, intuition eller opfindsomhed fra den person, der udfører handlingen
Tidligere i matematik blev det uformelle udtryk "effektivt beregnelig" brugt til at henvise til funktioner, der kan beregnes med blyant og papir. Men selve forestillingen om algoritmisk beregnelighed var mere intuitiv end noget konkret. Nu var den karakteriseret ved en funktion med et naturligt argument, som der er en beregningsalgoritme for. En af Alan Turings præstationer varrepræsentation af et formelt nøjagtigt prædikat, ved hjælp af hvilket det ville være muligt at erstatte det uformelle, hvis metodeeffektivitetsbetingelsen anvendes. Kirken gjorde den samme opdagelse.
Grundlæggende begreber for rekursive funktioner
Turings ændring af prædikater så ved første øjekast anderledes ud end den, hans kollega havde foreslået. Men som et resultat viste de sig at være ækvivalente i den forstand, at hver af dem vælger det samme sæt matematiske funktioner. Church-Turing-afhandlingen er påstanden om, at dette sæt indeholder enhver funktion, hvis værdier kan opnås ved en metode, der opfylder effektivitetsbetingelserne. Der var en anden forskel mellem de to opdagelser. Det var, at Church kun betragtede eksempler på positive heltal, mens Turing beskrev sit arbejde som at dække beregnelige funktioner med en integral eller reel variabel.
Almindelige rekursive funktioner
Kirkens oprindelige formulering siger, at beregningen kan udføres ved hjælp af λ-regningen. Dette svarer til at bruge generiske rekursive funktioner. Church-Turing-afhandlingen dækker flere former for beregninger end oprindeligt antaget. For eksempel relateret til cellulære automater, kombinatorer, registreringsmaskiner og substitutionssystemer. I 1933 lavede matematikerne Kurt Gödel og Jacques Herbrand en formel definition af en klasse kaldet generelle rekursive funktioner. Den bruger funktioner, hvor mere end ét argument er muligt.
Oprettelse af en metodeλ-calculus
I 1936 skabte Alonso Church en bestemmelsesmetode kaldet λ-regningen. Han var forbundet med naturlige tal. Inden for λ-regningen bestemte videnskabsmanden deres kodning. Som et resultat kaldes de kirkenumre. En funktion baseret på naturlige tal blev kaldt λ-beregnelig. Der var en anden definition. Funktionen fra Kirkens speciale kaldes λ-beregnbar under to forhold. Den første lød sådan her: hvis den blev beregnet på kirkelige elementer, og den anden betingelse var muligheden for at blive repræsenteret af et medlem af λ-regningen.
Også i 1936, før han studerede sin kollegas arbejde, skabte Turing en teoretisk model for de abstrakte maskiner, der nu er opkaldt efter ham. De kunne udføre beregninger ved at manipulere tegnene på båndet. Dette gælder også for andre matematiske aktiviteter, der findes i teoretisk datalogi, såsom kvantesandsynlighedsberegning. Funktionen fra Kirkens speciale blev først senere underbygget ved hjælp af en Turing-maskine. Til at begynde med stolede de på λ-calculus.
Funktionsberegnelighed
Når naturlige tal er korrekt kodet som tegnsekvenser, siges en funktion på naturlige tal at være Turing-beregner, hvis den abstrakte maskine fandt den nødvendige algoritme og udskrev denne funktion på bånd. Sådan en enhed, som ikke fandtes i 1930'erne, ville i fremtiden blive betragtet som en computer. Den abstrakte Turing-maskine og Churchs afhandling indvarslede en æra med udviklingcomputerenheder. Det blev bevist, at de klasser af funktioner, der formelt er defineret af begge videnskabsmænd, falder sammen. Derfor blev begge udsagn kombineret til ét. Beregningsfunktioner og Kirkens speciale havde også stor indflydelse på begrebet beregnelighed. De blev også et vigtigt værktøj til matematisk logik og bevisteori.
Begrundelse og problemer med metoden
Der er modstridende synspunkter om afhandlingen. Der blev indsamlet talrige beviser for "arbejdshypotesen" foreslået af Church og Turing i 1936. Men alle kendte metoder eller operationer til at opdage nye effektivt beregnelige funktioner fra givne var forbundet med metoder til at bygge maskiner, som ikke eksisterede dengang. For at bevise Church-Turing-tesen tager man udgangspunkt i, at enhver realistisk beregningsmodel er ækvivalent.
På grund af de mange forskellige analyser anses dette generelt for at være særligt stærkt bevis. Alle forsøg på mere præcist at definere den intuitive forestilling om en effektivt beregnelig funktion viste sig at være ækvivalente. Enhver analyse, der er blevet foreslået, har vist sig at udpege den samme klasse af funktioner, nemlig dem, der kan beregnes af Turing-maskiner. Men nogle beregningsmodeller viste sig at være mere effektive med hensyn til tids- og hukommelsesforbrug til forskellige opgaver. Senere blev det bemærket, at de grundlæggende begreber om rekursive funktioner og Kirkens tese er ret hypotetiske.
Afhandling M
Det er vigtigt at skelne mellem Turings afhandling og påstanden om, at alt, der kan beregnes af en computerenhed, kan beregnes af dens maskine. Den anden mulighed har sin egen definition. Gandhi kalder den anden sætning for "Thesis M". Det lyder sådan her: "Hvad der end kan beregnes af en enhed, kan beregnes af en Turing-maskine." I afhandlingens snævre forstand er det en empirisk påstand, hvis sandhedsværdi er ukendt. Turings afhandling og "afhandling M" er nogle gange forvirrede. Den anden version er stort set forkert. Forskellige betingede maskiner er blevet beskrevet, der kan beregne funktioner, der ikke er Turing-beregnerbare. Det er vigtigt at bemærke, at den første afhandling ikke omfatter den anden, men er i overensstemmelse med dens falskhed.
Omvendt implikation af afhandlingen
I beregningsbarhedsteori bruges Churchs afhandling som en beskrivelse af begrebet beregnelighed af en klasse af generelle rekursive funktioner. Amerikaneren Stephen Kleene gav en mere generel formulering. Han kaldte delvist rekursive alle delfunktioner, der kunne beregnes af algoritmer.
Omvendt implikation omtales almindeligvis som Kirkens omvendte tese. Det ligger i det faktum, at hver rekursiv funktion af positive heltal evalueres effektivt. I snæver forstand betegner et speciale blot en sådan mulighed. Og i bredere forstand abstraherer den fra spørgsmålet om, hvorvidt denne betingede maskine kan eksistere i den.
kvantecomputere
Begreberne beregnelige funktioner og Kirkens afhandling blev en vigtig opdagelse for matematik, maskinteori og mange andre videnskaber. Men teknologien har ændret sig meget og bliver ved med at blive bedre. Det antages, at kvantecomputere kan udføre mange almindelige opgaver med mindre tid end moderne. Men der er stadig spørgsmål, såsom stopproblemet. En kvantecomputer kan ikke svare på det. Og ifølge Church-Turing-afhandlingen er der heller ingen anden computerenhed.
