De belangrijkste machine die nooit is gebouwd

Berekening is een bekend concept dat de meesten van ons intuïtief begrijpen. Neem de functie f(x) = x + 3. Wanneer x is drie, f(3) = 3 + 3. Zes. Eenvoudig. Het lijkt voor de hand te liggen dat deze functie berekenbaar is. Maar sommige functies zijn niet zo eenvoudig, en het is niet zo eenvoudig om te bepalen of ze kunnen worden berekend, wat betekent dat ze ons misschien nooit een definitief antwoord zullen geven.

In 1928 stelden de Duitse wiskundigen David Hilbert en Wilhelm Ackermann een vraag voor genaamd de Beslissingsprobleem ("beslissingsprobleem"). Na verloop van tijd zou hun vraag leiden tot een formele definitie van berekenbaarheid, een die wiskundigen in staat stelde een groot aantal nieuwe problemen te beantwoorden en de basis legde voor theoretische informatica.

De definitie kwam van een 23-jarige afstudeerder genaamd Alan Turing, die in 1936 schreef een baanbrekend papier dat niet alleen het concept van berekening formaliseerde, maar ook een fundamentele vraag in de wiskunde bleek te zijn en de intellectuele basis legde voor de uitvinding van de elektronische computer. Het grote inzicht van Turing was om een ​​concreet antwoord te geven op de rekenvraag in de vorm van een abstracte machine, later de Turing-machine genoemd door zijn promovendus, Alonzo Church. Het is abstract omdat het fysiek niet bestaat (en niet kan) als een tastbaar apparaat. In plaats daarvan is het een conceptueel rekenmodel: als de machine een functie kan berekenen, dan is de functie berekenbaar.

Dit is hoe het werkt. Een Turing-machine kan symbolen op een oneindig lange band lezen en wijzigen, zoals voorgeschreven door een tabel met regels. De band bestaat uit "cellen", die elk precies één symbool kunnen opslaan, en de machine leest en herschrijft de inhoud van de cellen met een bandkop. Elke regel in de tabel bepaalt wat de machine moet doen op basis van zowel de huidige status als het symbool dat wordt gelezen. De machine kan in een eindtoestand komen ("accepteertoestand" of "weigeringstoestand") waarna hij stopt en de invoer accepteert of weigert. Of het valt in een oneindige lus en blijft de band voor altijd lezen.

De beste manier om een ​​Turing-machine te begrijpen, is door een eenvoudig voorbeeld te bekijken. Laten we ons er een voorstellen die is ontworpen om ons te vertellen of een bepaalde invoer het getal nul is. We gebruiken het invoernummer 0001 vergezeld van lege symbolen (#), dus "#0001#" is het relevante deel van onze band.

De machine start in de begintoestand, die we q0 zullen noemen. Het leest de meest linkse cel op onze band en vindt een lege ruimte. De regels zeggen: "In status q0, als het symbool # is, laat het zoals het is zonder wijziging, verplaats een cel naar rechts en verander de status van de machine in q1." Na deze stap bevindt de machine zich in toestand q1 en leest de kop het tweede symbool, 0.

Nu gaan we op zoek naar een regel die van toepassing is op deze voorwaarden. We vinden er een die zegt: "Blijf in toestand q1 en verplaats het hoofd één cel naar rechts." Dit laat ons in dezelfde positie (in toestand q1, lezen "0"), dus we blijven naar rechts bewegen totdat het hoofd uiteindelijk een ander nummer leest, de 1.

Als we de tabel opnieuw raadplegen, vinden we een nieuwe regel: "Als we een 1 tegenkomen, gaan we over naar q2, wat een 'afwijzende' toestand is." De machine stopt en antwoordt "Nee" op de oorspronkelijke vraag: "Is '0001' nul?"

Als in plaats daarvan de invoer "#0000#" is, zal de machine een # tegenkomen na al die nullen. Als we de tabel raadplegen, vinden we een regel die zegt dat dit betekent dat de machine in toestand q3 komt, een toestand "accepteren". Nu antwoordt de machine "Ja" op de vraag "Is '0000' nul?"

Met zijn abstracte machine ontwikkelde Turing een rekenmodel om het Entscheidungsproblem te beantwoorden, dat formeel vraagt: Bestaat er, gegeven een reeks wiskundige axioma's, een mechanisch proces - een reeks instructies, die we tegenwoordig een algoritme zouden noemen - dat altijd kan bepalen of een bepaalde bewering waar is?

Stel dat we een algoritme willen vinden dat ons kan vertellen of een bepaalde schaakstelling mogelijk is. Hier zijn de axioma's de schaakregels die legale zetten regelen. Kunnen we een eindige stapsgewijze reeks procedures volgen om tot die positie te komen? Hoewel sommige posities langer kunnen duren dan ons leven om te analyseren - een algoritme kan alle mogelijke posities genereren en ze allemaal vergelijken met de invoer - dergelijke algoritmen bestaan ​​in het schaakspel. Daarom zeggen we dat schaken "beslisbaar" is.

In 1936 hebben Church en Turing echter - met verschillende methoden - onafhankelijk van elkaar bewezen dat er geen algemene manier is om elk geval van het Entscheidungsprobleem op te lossen. Sommige games, zoals Game of Life van John Conway, zijn bijvoorbeeld onbeslisbaar: geen enkel algoritme kan bepalen of een bepaald patroon uit een initieel patroon zal verschijnen.

Turing toonde aan dat een functie berekenbaar is als er een algoritme bestaat dat de gewenste taak kan uitvoeren. Tegelijkertijd liet hij zien dat een algoritme een proces is dat kan worden gedefinieerd door een Turing-machine. Daarom is een berekenbare functie een functie die een Turing-machine heeft om deze te berekenen. Dit lijkt misschien een omslachtige manier om berekenbaarheid te definiëren, maar het is de beste die we hebben. "Het is niet alsof je de keuze hebt om het op een andere manier te definiëren," zei Michaël Sipser, een theoretisch computerwetenschapper aan het Massachusetts Institute of Technology. "Ik denk dat het algemeen wordt aanvaard dat de Church-Turing-these zegt dat de informele notie van algoritme overeenkomt met wat elk 'redelijk' rekenmodel kan doen." Andere wiskundigen hebben verschillende rekenmodellen bedacht die er op het eerste gezicht heel anders uitzien, maar eigenlijk gelijkwaardig zijn: ze kunnen elke berekening uitvoeren die Turing-machines kunnen, en vice versa.

Slechts een paar jaar nadat Kurt Gödel had bewezen dat wiskunde dat wel was incompleet, Church en Turing toonden met dit werk aan dat sommige problemen in de wiskunde onbeslisbaar zijn - geen enkel algoritme, hoe geavanceerd ook, kan ons vertellen of het antwoord ja of nee is. Beiden waren verwoestende slagen voor Hilbert, die had gehoopt dat wiskunde nette, geïdealiseerde antwoorden zou hebben. Maar het is misschien maar goed ook: als er een algemene oplossing voor het Entscheidungsprobleem zou bestaan, zou dat betekenen dat alle problemen in de wiskunde gereduceerd zouden kunnen worden tot eenvoudige mechanische berekeningen.

Naast het beantwoorden van deze fundamentele vragen, leidde de machine van Turing ook direct tot de ontwikkeling van moderne computers, via een variant die bekend staat als de universele Turing-machine. Dit is een speciaal soort Turing-machine die elke andere Turing-machine op elke invoer kan simuleren. Het kan een beschrijving lezen van andere Turing-machines (hun regels en invoerbanden) en hun gedrag simuleren op zijn eigen invoerband, waarbij dezelfde uitvoer wordt geproduceerd die de gesimuleerde machine zou produceren, net zoals de computers van vandaag elk programma kunnen lezen en uitvoeren. In 1945 stelde John von Neumann een computerarchitectuur voor - de von Neumann-architectuur genaamd - die het universele Turing-machineconcept mogelijk maakte in een echte machine.

. Sanjeev Arora, een theoretisch computerwetenschapper aan Princeton University, dit concept doceert, benadrukt hij een breder filosofisch beeld. "Er zijn twee noties van 'universeel'," zei hij. “Een idee van het universele is dat het elke andere Turing-machine kan aansturen. Maar de andere, grotere notie van 'universeel' is dat het elke berekening kan uitvoeren die je maar kunt bedenken in het universum." In de wereld van de klassieke fysica kan elk fysiek proces worden gemodelleerd of gesimuleerd met behulp van algoritmen, die op hun beurt kunnen worden gesimuleerd door een Turing-machine.

Een andere opmerkelijke en steeds bruikbare variant is de probabilistische Turing-machine. In tegenstelling tot een gewone Turing-machine - die een goed gedefinieerde reactie heeft op elke invoer - kan een probabilistische Turing-machine meerdere reacties hebben op basis van kansen. Dit betekent dat het verschillende resultaten kan opleveren voor dezelfde invoer op verschillende tijdstippen. Verrassend genoeg is dit soort probabilistische strategie kan voor bepaalde problemen efficiënter zijn dan een zuiver deterministische benadering. Het is aangetoond dat ideeën van probabilistische Turing-machines praktisch bruikbaar zijn op gebieden als cryptografie, optimalisatie en machine learning.

Deze abstracte machines zijn misschien wel het beste bewijs dat het stellen van fundamentele vragen een van de nuttigste dingen kan zijn die een wetenschapper kan doen.