De stelling van Church-Turing verwijst naar het concept van een efficiënte, systematische of mechanische methode in logica, wiskunde en informatica. Het is geformuleerd als een beschrijving van het intuïtieve concept van berekenbaarheid en wordt, in relatie tot algemene recursieve functies, vaker de stelling van de kerk genoemd. Het verwijst ook naar de theorie van computerberekenbare functies. Het proefschrift verscheen in de jaren dertig, toen computers zelf nog niet bestonden. Het werd later vernoemd naar de Amerikaanse wiskundige Alonso Church en zijn Britse collega Alan Turing.
Efficiëntie van de methode om het resultaat te bereiken
Het eerste apparaat dat op een moderne computer leek, was de Bombie, een machine gemaakt door de Engelse wiskundige Alan Turing. Het werd gebruikt om Duitse berichten te ontcijferen tijdens de Tweede Wereldoorlog. Maar voor zijn scriptie en formalisering van het concept van een algoritme gebruikte hij abstracte machines, later Turingmachines genoemd. scriptie presenteertinteressant voor zowel wiskundigen als programmeurs, aangezien dit idee de makers van de eerste computers inspireerde.
In de berekenbaarheidstheorie staat de Church-Turing-these ook bekend als het vermoeden over de aard van berekenbare functies. Het stelt dat voor elke algoritmisch berekenbare functie op natuurlijke getallen, er een Turing-machine is die deze kan berekenen. Of, met andere woorden, er is een algoritme dat er geschikt voor is. Een bekend voorbeeld van de effectiviteit van deze methode is de waarheidstabeltest voor het testen van tautologie.
Een manier om elk gewenst resultaat te bereiken wordt "effectief", "systematisch" of "mechanisch" genoemd als:
- De methode wordt gespecificeerd in termen van een eindig aantal exacte instructies, elke instructie wordt uitgedrukt met een eindig aantal karakters.
- Het zal zonder fouten werken, zal het gewenste resultaat opleveren in een bepaald aantal stappen.
- De methode kan worden uitgevoerd door een mens zonder hulp met andere apparatuur dan papier en potlood
- Het vereist geen begrip, intuïtie of vindingrijkheid van de persoon die de actie uitvoert
Eerder in de wiskunde werd de informele term 'effectief berekenbaar' gebruikt om te verwijzen naar functies die met potlood en papier kunnen worden berekend. Maar het hele idee van algoritmische berekenbaarheid was intuïtiever dan iets concreets. Nu werd het gekenmerkt door een functie met een natuurlijk argument, waarvoor een rekenalgoritme bestaat. Een van de prestaties van Alan Turing was:representatie van een formeel exact predikaat, met behulp waarvan het mogelijk zou zijn om het informele predikaat te vervangen, als de methode-efficiëntievoorwaarde wordt gebruikt. Church deed dezelfde ontdekking.
Basisconcepten van recursieve functies
Turing's wijziging van predikaten zag er op het eerste gezicht anders uit dan die voorgesteld door zijn collega. Maar als resultaat bleken ze equivalent te zijn, in die zin dat elk van hen dezelfde reeks wiskundige functies selecteert. De Church-Turing-these is de bewering dat deze set elke functie bevat waarvan de waarden kunnen worden verkregen met een methode die voldoet aan de efficiëntievoorwaarden. Er was nog een verschil tussen de twee ontdekkingen. Het was dat Church alleen voorbeelden van positieve gehele getallen beschouwde, terwijl Turing zijn werk beschreef als het bestrijken van berekenbare functies met een integrale of reële variabele.
Algemene recursieve functies
De oorspronkelijke formulering van Church stelt dat de berekening kan worden gedaan met behulp van de λ-calculus. Dit komt overeen met het gebruik van generieke recursieve functies. De stelling van Church-Turing omvat meer soorten berekeningen dan aanvankelijk werd gedacht. Bijvoorbeeld gerelateerd aan cellulaire automaten, combinators, registratiemachines en substitutiesystemen. In 1933 creëerden wiskundigen Kurt Gödel en Jacques Herbrand een formele definitie van een klasse die algemene recursieve functies wordt genoemd. Het gebruikt functies waar meer dan één argument mogelijk is.
Een methode makenλ-calculus
In 1936 creëerde Alonso Church een bepalingsmethode die de λ-calculus wordt genoemd. Hij werd geassocieerd met natuurlijke getallen. Binnen de λ-calculus bepaalde de wetenschapper hun codering. Daarom worden ze kerknummers genoemd. Een functie gebaseerd op natuurlijke getallen werd λ-berekenbaar genoemd. Er was een andere definitie. De functie uit de stelling van Church wordt λ-berekenbaar genoemd onder twee voorwaarden. De eerste klonk als volgt: als het werd berekend op basis van kerkelijke elementen, en de tweede voorwaarde was de mogelijkheid om vertegenwoordigd te worden door een lid van de λ-calculus.
Ook in 1936, voordat hij het werk van zijn collega bestudeerde, creëerde Turing een theoretisch model voor de abstracte machines die nu naar hem vernoemd zijn. Ze konden berekeningen uitvoeren door de karakters op de band te manipuleren. Dit geldt ook voor andere wiskundige activiteiten in de theoretische informatica, zoals quantum probabilistic computing. De functie uit de stelling van Church werd pas later onderbouwd met een Turingmachine. Aanvankelijk vertrouwden ze op λ-calculus.
Functieberekenbaarheid
Als natuurlijke getallen op de juiste manier worden gecodeerd als tekenreeksen, wordt gezegd dat een functie op natuurlijke getallen Turing-berekenbaar is als de abstracte machine het vereiste algoritme heeft gevonden en deze functie op tape heeft afgedrukt. Een dergelijk apparaat, dat in de jaren dertig nog niet bestond, zou in de toekomst als een computer worden beschouwd. De abstracte Turingmachine en de stelling van Church luidden een tijdperk van ontwikkeling incomputer apparaten. Het werd bewezen dat de klassen van functies die formeel door beide wetenschappers zijn gedefinieerd, samenvallen. Daarom zijn beide uitspraken samengevoegd tot één. Computationele functies en de stelling van Church hadden ook een sterke invloed op het concept van berekenbaarheid. Ze werden ook een belangrijk hulpmiddel voor wiskundige logica en bewijstheorie.
Rechtvaardiging en problemen van de methode
Er zijn tegenstrijdige opvattingen over het proefschrift. Er werd veel bewijs verzameld voor de 'werkhypothese' die door Church en Turing in 1936 werd voorgesteld. Maar alle bekende methoden of bewerkingen voor het ontdekken van nieuwe, effectief berekenbare functies van gegeven functies waren verbonden met methoden om machines te bouwen, die toen nog niet bestonden. Om de stelling van Church-Turing te bewijzen, gaat men ervan uit dat elk realistisch rekenmodel equivalent is.
Vanwege de verscheidenheid aan verschillende analyses wordt dit over het algemeen als bijzonder sterk bewijs beschouwd. Alle pogingen om het intuïtieve begrip van een effectief berekenbare functie nauwkeuriger te definiëren, bleken gelijkwaardig te zijn. Elke analyse die is voorgesteld, heeft bewezen dezelfde klasse van functies te onderscheiden, namelijk die welke door Turing-machines kunnen worden berekend. Maar sommige rekenmodellen bleken efficiënter te zijn in termen van tijd- en geheugengebruik voor verschillende taken. Later werd opgemerkt dat de basisconcepten van recursieve functies en de stelling van de kerk nogal hypothetisch zijn.
Thesis M
Het is belangrijk om onderscheid te maken tussen de stelling van Turing en de bewering dat alles wat kan worden berekend door een computerapparaat, kan worden berekend door zijn machine. De tweede optie heeft zijn eigen definitie. Gandhi noemt de tweede zin "Thesis M". Het gaat als volgt: "Alles wat kan worden berekend door een apparaat, kan worden berekend door een Turing-machine." In de enge zin van het proefschrift is het een empirische propositie waarvan de waarheidswaarde onbekend is. Turing's Thesis en "Thesis M" worden soms verward. De tweede versie is grotendeels onjuist. Er zijn verschillende conditionele machines beschreven die functies kunnen berekenen die niet Turing-berekenbaar zijn. Het is belangrijk op te merken dat de eerste stelling niet de tweede inhoudt, maar consistent is met de onjuistheid ervan.
Omgekeerde implicatie van het proefschrift
In de berekenbaarheidstheorie wordt de stelling van Church gebruikt als een beschrijving van het begrip berekenbaarheid door een klasse van algemene recursieve functies. De Amerikaan Stephen Kleene gaf een meer algemene formulering. Hij noemde gedeeltelijk recursief alle gedeeltelijke functies die berekenbaar zijn door algoritmen.
Omgekeerde implicatie wordt gewoonlijk de omgekeerde stelling van de kerk genoemd. Het ligt in het feit dat elke recursieve functie van positieve gehele getallen efficiënt wordt geëvalueerd. In enge zin duidt een proefschrift gewoon op een dergelijke mogelijkheid. En in bredere zin abstraheert het van de vraag of deze voorwaardelijke machine erin kan bestaan.
Kwantumcomputers
De concepten van berekenbare functies en de stelling van de kerk werden een belangrijke ontdekking voor wiskunde, machinetheorie en vele andere wetenschappen. Maar de technologie is veel veranderd en blijft verbeteren. Aangenomen wordt dat kwantumcomputers veel voorkomende taken in minder tijd kunnen uitvoeren dan moderne. Maar er blijven vragen, zoals het stopprobleem. Een kwantumcomputer kan het niet beantwoorden. En, volgens de stelling van Church-Turing, ook geen ander computerapparaat.
