The Church-Turing-avhandlingen hänvisar till konceptet med en effektiv, systematisk eller mekanisk metod inom logik, matematik och datavetenskap. Den är formulerad som en beskrivning av det intuitiva begreppet beräkningsbarhet och kallas i förhållande till generella rekursiva funktioner oftare för kyrkans avhandling. Det hänvisar också till teorin om datorberäknade funktioner. Avhandlingen dök upp på 1930-talet, när själva datorerna ännu inte existerade. Den fick senare sitt namn efter den amerikanske matematikern Alonso Church och hans brittiske kollega Alan Turing.
Metodens effektivitet för att uppnå resultatet
Den första enheten som liknade en modern dator var Bombie, en maskin skapad av den engelske matematikern Alan Turing. Den användes för att dechiffrera tyska meddelanden under andra världskriget. Men för sin avhandling och formalisering av begreppet en algoritm använde han abstrakta maskiner, senare kallade Turing-maskiner. Examensarbete presenterarintresse för både matematiker och programmerare, eftersom denna idé inspirerade skaparna av de första datorerna.
I beräkningsbarhetsteorin är Church-Turing-avhandlingen också känd som gissningen om beräkningsbara funktioners natur. Den säger att för alla algoritmiskt beräkningsbara funktioner på naturliga tal finns det en Turing-maskin som kan beräkna den. Eller, med andra ord, det finns en algoritm som är lämplig för det. Ett välkänt exempel på effektiviteten av denna metod är sanningstabellstestet för att testa tautologi.
Ett sätt att uppnå önskat resultat kallas "effektivt", "systematisk" eller "mekaniskt" om:
- Metoden specificeras i termer av ett ändligt antal exakta instruktioner, varje instruktion uttrycks med ett ändligt antal tecken.
- Det kommer att köras utan fel, ger önskat resultat i ett visst antal steg.
- Metoden kan utföras av en människa utan hjälp med annan utrustning än papper och penna
- Det kräver inte förståelse, intuition eller uppfinningsrikedom från den person som utför handlingen
Tidigare inom matematiken användes den informella termen "effektivt beräkningsbar" för att referera till funktioner som kan beräknas med penna och papper. Men själva begreppet algoritmisk beräkningsbarhet var mer intuitivt än något konkret. Nu kännetecknades den av en funktion med ett naturligt argument, för vilket det finns en beräkningsalgoritm. En av Alan Turings prestationer varrepresentation av ett formellt exakt predikat, med vars hjälp det skulle vara möjligt att ersätta det informella, om metoden effektivitetsvillkor används. Church gjorde samma upptäckt.
Grundläggande begrepp för rekursiva funktioner
Turings byte av predikat såg vid första anblicken annorlunda ut än det som hans kollega föreslagit. Men som ett resultat visade de sig vara likvärdiga, i den meningen att var och en av dem väljer samma uppsättning matematiska funktioner. Church-Turing-avhandlingen är påståendet att denna uppsättning innehåller varje funktion vars värden kan erhållas med en metod som uppfyller effektivitetsvillkoren. Det fanns en annan skillnad mellan de två upptäckterna. Det var så att kyrkan bara betraktade exempel på positiva heltal, medan Turing beskrev sitt arbete som att täcka beräkningsbara funktioner med en integral eller reell variabel.
Vanliga rekursiva funktioner
Kyrkans ursprungliga formulering säger att beräkningen kan göras med hjälp av λ-kalkylen. Detta motsvarar att använda generiska rekursiva funktioner. Church-Turing-avhandlingen täcker fler typer av beräkningar än vad man ursprungligen trodde. Till exempel relaterat till cellulära automater, kombinatorer, registreringsmaskiner och substitutionssystem. 1933 skapade matematikerna Kurt Gödel och Jacques Herbrand en formell definition av en klass som kallas allmänna rekursiva funktioner. Den använder funktioner där mer än ett argument är möjligt.
Skapa en metodλ-kalkyl
År 1936 skapade Alonso Church en metod för bestämning som kallas λ-kalkyl. Han förknippades med naturliga tal. Inom λ-kalkylen bestämde forskaren deras kodning. Som ett resultat kallas de för kyrkonummer. En funktion baserad på naturliga tal kallades λ-beräknbar. Det fanns en annan definition. Funktionen från kyrkans avhandling kallas λ-beräknbar under två förutsättningar. Det första lät så här: om det beräknades på kyrkliga element, och det andra villkoret var möjligheten att representeras av en medlem av λ-kalkylen.
Också 1936, innan han studerade sin kollegas arbete, skapade Turing en teoretisk modell för de abstrakta maskiner som nu är uppkallade efter honom. De kunde utföra beräkningar genom att manipulera tecknen på bandet. Detta gäller även andra matematiska aktiviteter som finns inom teoretisk datavetenskap, såsom kvantprobabilistisk beräkning. Funktionen från kyrkans avhandling underbyggdes först senare med en Turingmaskin. Till en början förlitade de sig på λ-kalkyl.
Funktionsberäknarbarhet
När naturliga tal är korrekt kodade som teckensekvenser, sägs en funktion på naturliga tal vara Turing-beräknad om den abstrakta maskinen hittade den nödvändiga algoritmen och skrev ut denna funktion på band. En sådan anordning, som inte fanns på 1930-talet, skulle i framtiden betraktas som en dator. Den abstrakta Turing-maskinen och kyrkans avhandling förebådade en era av utvecklingdatorenheter. Det bevisades att de klasser av funktioner som formellt definierats av båda forskarna sammanfaller. Därför, som ett resultat, kombinerades båda uttalandena till ett. Beräkningsfunktioner och kyrkans avhandling hade också ett starkt inflytande på begreppet beräkningsbarhet. De blev också ett viktigt verktyg för matematisk logik och bevisteori.
Motivering och problem med metoden
Det finns motstridiga åsikter om avhandlingen. Många bevis samlades in för den "arbetshypotes" som föreslogs av Church och Turing 1936. Men alla kända metoder eller operationer för att upptäcka nya effektivt beräkningsbara funktioner från givna var kopplade till metoder för att bygga maskiner, som inte fanns då. För att bevisa Church-Turing-tesen utgår man från det faktum att varje realistisk beräkningsmodell är likvärdig.
På grund av mångfalden av olika analyser anses detta i allmänhet vara särskilt starkt bevis. Alla försök att mer exakt definiera den intuitiva uppfattningen om en effektivt beräkningsbar funktion visade sig vara likvärdiga. Varje analys som har föreslagits har visat sig peka ut samma klass av funktioner, nämligen de som är beräkningsbara av Turing-maskiner. Men vissa beräkningsmodeller visade sig vara mer effektiva när det gäller tid och minnesanvändning för olika uppgifter. Senare noterades att de grundläggande begreppen rekursiva funktioner och kyrkans tes är ganska hypotetiska.
Thesis M
Det är viktigt att skilja mellan Turings avhandling och påståendet att allt som kan beräknas av en datorenhet kan beräknas av dess maskin. Det andra alternativet har sin egen definition. Gandhi kallar den andra meningen "Thesis M". Det går så här: "Vad som än kan beräknas av en enhet kan beräknas av en Turing-maskin." I avhandlingens snäva bemärkelse är det ett empiriskt påstående vars sanningsvärde är okänt. Turings tes och "Thesis M" är ibland förvirrade. Den andra versionen är i stort sett felaktig. Olika villkorliga maskiner har beskrivits som kan beräkna funktioner som inte är Turing-beräknbara. Det är viktigt att notera att den första avhandlingen inte innehåller den andra, utan överensstämmer med dess falskhet.
Omvänd implikation av avhandlingen
I beräkningsbarhetsteorin används kyrkans avhandling som en beskrivning av begreppet beräkningsbarhet av en klass av generella rekursiva funktioner. Amerikanen Stephen Kleene gav en mer allmän formulering. Han kallade partiellt rekursivt för alla delfunktioner som kan beräknas med algoritmer.
Omvänd implikation kallas vanligtvis kyrkans omvända tes. Det ligger i det faktum att varje rekursiv funktion av positiva heltal utvärderas effektivt. I en snäv mening betecknar en avhandling helt enkelt en sådan möjlighet. Och i en vidare mening abstraherar den från frågan om denna villkorsmaskin kan existera i den.
Quantum-datorer
Begreppen beräkningsbara funktioner och kyrkans avhandling blev en viktig upptäckt för matematik, maskinteori och många andra vetenskaper. Men tekniken har förändrats mycket och fortsätter att förbättras. Det antas att kvantdatorer kan utföra många vanliga uppgifter med mindre tid än moderna. Men frågor kvarstår, som stoppproblemet. En kvantdator kan inte svara på det. Och enligt Church-Turing-avhandlingen, ingen annan datorenhet heller.
