Alan Turing en de kracht van negatief denken

Het diagonalisatiebewijs van Turing is een versie van dit spel waarbij de vragen door de oneindige lijst van mogelijke algoritmen lopen, waarbij herhaaldelijk wordt gevraagd: “Kan dit algoritme het probleem oplossen waarvan we graag willen dat het onberekenbaar is?”

“Het zijn een soort oneindige vragen”, zei Williams.

Om het spel te winnen moest Turing een probleem bedenken waarbij het antwoord voor elk algoritme nee is. Dat betekende het identificeren van een bepaalde invoer die ervoor zorgt dat het eerste algoritme het verkeerde antwoord geeft, een andere invoer die ervoor zorgt dat de tweede mislukt, enzovoort. Hij vond die speciale input met behulp van een truc die leek op de truc die Kurt Gödel onlangs had gebruikt om te bewijzen dat zelfreferentiële beweringen als ‘deze bewering is onbewijsbaar’ problemen opleverden voor de grondslagen van de wiskunde.

Het belangrijkste inzicht was dat elk algoritme (of programma) kan worden weergegeven als een reeks nullen en enen. Dat betekent, net als in het voorbeeld van het foutcontroleprogramma, dat een algoritme de code van een ander algoritme als invoer kan nemen. In principe kan een algoritme zelfs zijn eigen code als invoer nemen.

Met dit inzicht kunnen we een onberekenbaar probleem definiëren zoals dat in het bewijs van Turing: “Gegeven een invoerreeks die de code van een algoritme vertegenwoordigt, is de output 1 als dat algoritme 0 oplevert als zijn eigen code de invoer is; anders uitgang 0.” Elk algoritme dat dit probleem probeert op te lossen, zal de verkeerde uitvoer produceren op ten minste één invoer, namelijk de invoer die overeenkomt met zijn eigen code. Dat betekent dat dit perverse probleem door geen enkel algoritme kan worden opgelost.

Wat ontkenning niet kan doen

Computerwetenschappers waren nog niet klaar met diagonalisering. In 1965 pasten Juris Hartmanis en Richard Stearns het argument van Turing aan om te bewijzen dat niet alle berekenbare problemen gelijk zijn geschapen – sommige zijn intrinsiek moeilijker dan andere. Dat resultaat lanceerde het veld van de computationele complexiteitstheorie, die de moeilijkheidsgraad van computationele problemen bestudeert.

Maar de complexiteitstheorie bracht ook de grenzen van Turings tegengestelde methode aan het licht. In 1975 bewezen Theodore Baker, John Gill en Robert Solovay dat veel open vragen in de complexiteitstheorie nooit kunnen worden opgelost door alleen diagonalisatie. De belangrijkste hiervan is het beroemde P versus NP-probleem, dat de vraag stelt of alle problemen met gemakkelijk te controleren oplossingen ook gemakkelijk op te lossen zijn met het juiste ingenieuze algoritme.

De blinde vlekken van diagonalisering zijn een direct gevolg van het hoge abstractieniveau dat haar zo krachtig maakt. Het bewijs van Turing bracht geen onberekenbaar probleem met zich mee dat zich in de praktijk zou kunnen voordoen; in plaats daarvan werd zo’n probleem ter plekke bedacht. Andere bewijzen van diagonalisatie staan ​​op dezelfde manier afzijdig van de echte wereld, zodat ze geen vragen kunnen oplossen waarbij details uit de echte wereld ertoe doen.

“Ze verwerken berekeningen op afstand”, zei Williams. “Ik stel me een man voor die met virussen te maken heeft en deze via een of ander handschoenenkastje benadert.”

Het mislukken van de diagonalisatie was een vroege indicatie dat het oplossen van het P versus NP-probleem een ​​lange reis zou zijn. Maar ondanks de beperkingen blijft diagonalisering een van de belangrijkste instrumenten in het arsenaal van complexiteitstheoretici. In 2011 gebruikte Williams het samen met een hele reeks andere technieken om te bewijzen dat een bepaald beperkt rekenmodel een aantal buitengewoon moeilijke problemen niet kon oplossen – een resultaat dat onderzoekers al 25 jaar ontgaan was. Het was verre van een oplossing van P versus NP, maar het betekende nog steeds een grote vooruitgang.

Als je wilt bewijzen dat iets niet mogelijk is, onderschat dan niet de kracht van gewoon nee zeggen.

Origineel verhaal herdrukt met toestemming van Quanta-tijdschrift, een redactioneel onafhankelijke publicatie van de Simons Stichting wiens missie het is om het publieke begrip van wetenschap te vergroten door onderzoeksontwikkelingen en trends in de wiskunde en de natuur- en levenswetenschappen te behandelen.