Mijn favoriete auteurs (David Deutsch, Roger Penrose, en Douglas Hofstadter) duiken allemaal in de kerk-Turing Thesis van de computationele theorie en, nog belangrijker, de sterkste interpretatie ervan: Het Turing Principe. In dit artikel zal ik eerst de kerk-Turing Thesis uitleggen in termen van leken.
toen ik werkte aan mijn Computer Science diploma studeerde ik Turing machines en de kerk-Turing Thesis in mijn Intro tot computationele theorie klasse. Toen dacht ik dat het tijdverspilling was. Ik wilde alleen maar computers programmeren en ik kon me niet schelen over deze lang-dode Turing kerel (noch deze kerk kerel) noch zijn domme theoretische machines.
nu ik de filosofische vertakkingen van de kerk-Turing Thesis begrijp, wou ik dat ik had opgelet in de klas! Want de kerk-Turing Thesis, als het waar is, heeft een aantal diepgaande filosofische vertakkingen en het zou ons ook iets kunnen vertellen over de diepe — en speciale — aard van de werkelijkheid.
eindige automaten
alle teksten en klassen over de Rekentheorie beginnen met iets dat “eindige automaten” wordt genoemd.”Het basisidee erachter is vrij eenvoudig. Je stelt je gewoon een eenvoudige ‘machine’ voor die keuzes kan maken en tussen staten kan bewegen. Hier is een voorbeeld van een zeer eenvoudige die de “logica” van een muntaangedreven tourniquet vertegenwoordigt.
in gewoon Engels betekent dit dat als je probeert door een draaischijf te duwen die vergrendeld is, je dat niet kunt als je niet eerst een munt hebt geplaatst. Als u in een munt hebt gezet, maar nog niet geduwd door nog, extra munten gewoon laat het in een ontgrendelde staat. Als je er een munt in hebt gedaan, dan kun je doorzetten. Het sluit dan weer voor de volgende persoon.
het was waarschijnlijk gemakkelijker te begrijpen uit het diagram dan uit de beschrijving.Eindige automaten zijn in staat om veel ingewikkelder logica uit te voeren dan deze. Maar dit zou je een basisgevoel moeten geven voor hoe eindige automaten werken.
een ding om op te merken is dat een eindige automaat, zoals hierboven, puur theoretisch is omdat het alleen bestaat als een bos bellen en lijnen op een stuk papier. Het is niet zo dat er een kleine “eindige automaat machine” in het draaihek die deze beslissingen neemt. Of misschien moet ik in plaats daarvan zeggen dat het draaipunt zelf de eindige automaatmachine is.
als we dat echt zouden willen, zouden we waarschijnlijk in het echt een machine kunnen bouwen die een eindige automaat zou zijn.Er is niets dat iemand ervan weerhoudt om het in het echte leven als een echte machine te bouwen en het vervolgens in het draaikruis te installeren. Dat is gewoon niet de goedkoopste manier om het te doen.
dus elk ‘programma’ dat je maakt als een tekening van een eindige automaat kan worden omgezet in een echte “berekening” die echt werkt. Het belang van het verschil tussen een computermachine die daadwerkelijk kan bestaan (zoals een eindige automaat) en een machine die slechts hypothetisch is en de wetten van de fysica schendt, wordt in een ogenblik belangrijk.
krachtigere Machines
naarmate een klasse in de computationele theorie vordert, worden de studenten geà ntroduceerd in steeds complexere ‘machines’ die krachtiger zijn dan eindige automaten. Zoals de figuur rechts laat zien, is de op één na krachtigste Pushdown Automata (PDA). Een PDA is eigenlijk gewoon een DFA met de toevoeging van een soort”geheugen”. Dit geheugen staat een PDA toe om berekeningen (of programma ‘s) te maken en uit te voeren die een DFA niet kan.
het belangrijkste punt is alleen dat er bepaalde soorten programma’ s zijn die geschreven kunnen worden voor een PDA die niet geschreven kunnen worden op een deterministische eindige automaat (DFA). Met andere woorden, PDA ’s zijn’ krachtiger ‘dan Dfa’ s omdat ze klassen van “programma ‘ s” kunnen uitdrukken die Dfa ’s niet kunnen.
er is dus een relatie tussen Dfa’ s en PDA ‘ s in termen van “rekenkracht.”Het is namelijk mogelijk om aan te tonen dat elk programma dat op een DFA geschreven wordt ook op een PDA geschreven kan worden, maar dat het omgekeerde niet waar is.
het bewijs is in het bewijs
het bewijs dat een PDA alles kan draaien wat een DFA kan worden gedaan door een schema te bedenken waarmee de logica van een DFA kan worden toegewezen aan een PDA. Aangezien een PDA gewoon een DFA met geheugen is, is dit niet moeilijk te doen — gebruik alleen de “memory feature”niet.
maar hoe zit het met het omgekeerde? Kunnen we bewijzen dat het onmogelijk is om bepaalde soorten “programma ‘ s” geschreven voor een PDA te vertalen naar een DFA? Dat wil zeggen, is er een bewijs dat Pushdown Automata niet kan worden gekoppeld aan een eindige Automata? Of gaan we ervan uit dat een eindige automaat minder krachtig is dan een Pushdown Automaat omdat we momenteel geen manier weten om een PDA terug te brengen naar een FDA? Misschien is er een manier om PDA ’s in kaart te brengen naar FDA’ s en misschien heeft niemand ontdekt hoe dat te doen? Is dat niet op zijn minst een mogelijkheid?
het blijkt dat het mogelijk is om aan te tonen dat een PDA bepaalde soorten programma ‘ s kan draaien die een DFA niet kan uitvoeren. De manier waarop je het zou doen is dat je een berekening (d.w.z. een programma) dat je kunt bewijzen dat een DFA niet kan berekenen en dan kunt aantonen dat een PDA het kan berekenen.
rekenkracht van een Machine
dit feit — dat er meer krachtige (PDA) en minder krachtige (DFA) logische machines zijn — is op zichzelf interessant.
maar het leidt tot een filosofische vraag: bestaat er zoiets als een ” meest krachtige computer?”
als er zo ‘ n “meest krachtige machine” was, hoe zouden we dan weten dat een specifieke voorgestelde machine “de meest krachtige machine” is?”Of zijn er gewoon verschillende soorten computers beschikbaar en moet je de juiste voor de baan kiezen?
Turingmachines
welke machine is krachtiger dan een PDA?
zoals de geschiedenis het zou zeggen, werden op ongeveer hetzelfde moment twee zeer verschillende typen “machines” voorgesteld die beide aantoonbaar krachtiger waren dan PDA ‘ s.
Eén was de Turingmachine van Alan Turing. De andere was niet zozeer een machine, maar een slimme set van notaties ontwikkeld door Alonzo Church die hetzelfde doel diende als het ontwikkelen van een machine. Van deze twee “machines” is de Turing machine conceptueel makkelijker te onderwijzen, dus meestal is dat de machine die wordt onderwezen in een computationele theorie cursus.
Turingmachines zijn grappige kleine theoretische machines met een lees – / schrijfkop en een (hypothetische) papieren tape waarvan het kan lezen of schrijven. Gebaseerd op wat de Turing Machine leest, brengt het de Turing Machine in een actie staat die een soort van combinatie van taken uitvoert bestaande uit het verplaatsen van de lees/schrijf kop vooruit of achteruit, het lezen van een nieuwe positie op de tape, of het schrijven dus een nieuwe positie op de tape. Een Turing Machine ziet er zo uit:
Turing Machines en Moderne Computers
Één ding van belang is dat een Turing Machine is, ondanks de verschijningen, eigenlijk heel vergelijkbaar met een moderne computer. In een moderne computer is de centrale verwerkingseenheid (CPU) gelijk aan de lees/schrijfkop van een Turingmachine. De geheugenchips (RAM of ROM) lijken erg op de cellen van de lange papieren tape waar de draaimachine van kan lezen of schrijven. Moderne computers lijken dus ongeveer gelijk te zijn aan een Turingmachine.
een moderne computer heeft één voordeel ten opzichte van de Turing-Machine. Een moderne computer hoeft niet van één cel van zijn “geheugen” in sequentiële volgorde te bewegen zoals een Turingmachine dat doet.
het feit dat een Turingmachine slechts één cel tegelijk kan verplaatsen lijkt een belangrijke beperking, nietwaar? We zagen net hoe sommige machines logischerwijs ‘krachtiger’ zijn dan andere: een PDA kan computationele taken uitvoeren die een FDA niet kan. Dus misschien zijn er machines die krachtiger zijn dan Turing machines die taken kunnen uitvoeren die Turing Machines niet kunnen? En misschien kan de moderne computer — vanwege hun vermogen om te springen rond het geheugen in plaats van sequentieel te verplaatsen van cel naar cel-een aantal programma ‘ s draaien die een Turing Machine niet kan?In feite heeft de moderne computer in feite minder expressief vermogen dan een Turingmachine, omdat Turingmachines werden opgevat als zijnde voorzien van een oneindig lang papierband (d.w.z. oneindig geheugen), waar een echte computer altijd een eindig geheugen zal hebben. In het algemeen maakt dit echter weinig verschil in welke soorten berekeningen men kan uitvoeren, aangezien mensen over het algemeen niet zo geïnteresseerd zijn in oneindig lange berekeningen die oneindig lange resultaten geven. Daarom zeg ik dat moderne computers en Turingmachines “ruwweg” gelijkwaardig zijn. In feite, zolang je elke willekeurige maar eindige grootte van het geheugen aanneemt, zijn ze precies gelijkwaardig in termen van welke soorten programma ‘ s ze kunnen draaien.
The Church Turing Thesis: Turing Machine = Max logische kracht
maar hoe zit het met de arme Alonzo Church? Zijn arme kleine” machine ” vergeten omdat Turing Machines zijn gemakkelijker te onderwijzen. Is zijn machine misschien in staat om berekeningen /programma ‘ s uit te drukken die een Turing Machine niet kan, of vice versa?Zou het geen toeval zijn als Alan Turing en Alonzo Church zo toevallig twee totaal verschillende typen theoretische rekenmachines creëerden en het zo gebeurde dat ze precies identiek waren in termen van welke soorten berekeningen ze konden uitvoeren?Dus stel je ieders verbazing voor toen Alan Turing in staat was om een bewijs te leveren dat elk programma geschreven voor een Turing Machine ook geschreven kon worden voor een kerk machine en ook een bewijs dat elk programma geschreven voor een kerk machine ook geschreven kon worden voor een Turing machine.
in feite zijn er een aantal voorgestelde typen theoretische rekenmachines. Theoretici probeerden bijvoorbeeld toe te staan dat een Turing Machine meerdere tapes had om mee te lezen/schrijven. Ze probeerden zelfs een Turing Machine een 2-dimensionaal ‘blad’ toe te staan om mee te lezen en te schrijven. Theoretici probeerden allerlei verbeteringen aan Turing Machines (en Kerk machines).
en tot nu toe was het mogelijk om voor elk van hen een bewijs te leveren dat ze gelijkwaardig zijn aan een eenvoudige Turingmachine.
dat lijkt een wild toeval, nietwaar? En het zou een wild toeval zijn, tenzij er een bovengrens is beperkt tot welke soorten berekeningen kunnen worden uitgevoerd.
als er zo ‘ n bovengrens is, dan zou het helemaal geen toeval zijn dat de Turing Machine en de Church Machine en alle andere computermachines toevallig allemaal dezelfde rekenkracht hebben, omdat in feite de reden waarom ze allemaal gelijkwaardig zijn, is omdat we de bovengrens van de rekenkracht hebben bereikt.
maar kunnen we bewijzen dat er geen computer bestaat — een die we nog niet hebben ontdekt — die de mogelijkheid heeft om berekeningen uit te voeren die een Turing Machine niet kan?
hoe zouden we zo ‘ n bewijs kunnen leveren? Feit is dat we niet kunnen bewijzen dat er niets krachtiger is dan een Turing Machine. Dus, wie weet, misschien wel.
maar feit is dat we dergelijke machines niet kunnen vinden (of uitvinden).Na veel moeite om de kracht van Turingmachines te verbeteren en te hebben gefaald, werd uiteindelijk de kerk-Turing Thesis aanvaard, ook al bleek het niet waar te zijn. De kerk-Turing Thesis zegt in wezen zoiets als dit:
het is niet mogelijk om te komen met een soort van computationele machine die een logisch programma kan uitvoeren dat een gewone oude Turing Machine niet kan.
of met andere woorden:
Turingmachines en hun equivalenten zijn de krachtigste mogelijke soorten rekenmachines en er zijn geen krachtigere die we nog niet kennen.
na jaren van onderzoek op dit proefschrift is dit proefschrift nog steeds geldig. We zullen later zien dat er enigszins een wijziging in de Thesis is geweest met de introductie van theoretische kwantumcomputers. Maar in principe geldt deze stelling nog steeds. Niemand heeft ooit een manier bedacht om Turing machines te overtreffen als het gaat om logische expressiviteit. Turing Machines zijn nog steeds de regerend kampioen.
dus nu begrijp je de kerk-Turing Thesis. Echter, de kerk-Turing Thesis is niet echt gelijk aan het Turing Principe. Dus in een toekomstige post Zal Ik ontwikkelen wat het verschil is en wat het filosofische vertakkingen zijn.
Opmerkingen
Het Turing-Beginsel. Zo genoemd door Roger Penrose, die er niet in gelooft (althans niet in de huidige vorm). Het werd ontwikkeld tot het Turing-Deutsch Principe door David Deutsch, die er wel in gelooft, althans in zijn vorm ervan.) (Zie artikel in Wikipedia voor meer details)