Bestaan er problemen die computers niet kunnen oplossen?

Informatie, entertainment, werk, onderwijs, snelle oplossingen voor complexe problemen... over het algemeen hebben we een vrij goed idee van wat we willen als we een computer gebruiken. Sterker nog, er zijn momenten waarop een systeem alles lijkt te kunnen oplossen, en dat leidt ons naar een zeer interessante logische oefening: Stel je een computer voor met oneindige tijd, energie en verwerkingskracht. Bestaat er iets dat hij zelfs met deze voordelen niet kan oplossen? Het korte antwoord is "ja", maar voor de rest hebben we de hulp van Tom Scott nodig...

Hoe vaak is het gebeurd? Een eenvoudige vraag werpt ons in een zwart gat van logica en rede. De wiskundige David Hilbert (dezelfde van het oneindige hotel) zat samen met zijn collega Wilhelm Ackermann in 1928 in die situatie, het jaar waarin beiden de uitdaging van het Entscheidungsproblem of "Beslissingsprobleem" presenteerden. In extreem losse bewoordingen stelt het probleem het volgende: Is het mogelijk om te bepalen of een gegeven verklaring of zin bewijsbaar is of niet? Met genoeg tijd en energie, kunnen we het antwoord op alles vinden?

Nu, wat heeft dit met computers te maken? In werkelijkheid kan die twijfel van Hilbert op een heel bijzondere manier aan het computeruniversum worden aangepast: Stel je de code van een programma voor, elk programma. Is het mogelijk om die code te analyseren en automatisch te bepalen of het zal stoppen of in een oneindige lus terechtkomt? Op dit punt stelt iemand een voorbeeld voor als:

10 PRINT “HOLA MUNDO”
20 GOTO 10
RUN

Uiteraard leidt dit stuk code tot een oneindige lus... maar het verschil is dat het zo is ontworpen. Bepalen of sommige programma's stoppen of voor altijd doorgaan, dat is gemakkelijk. Het idee om elke code, alle codes te nemen en te analyseren om definitief vast te stellen of ze eindigen of in een lus gaan, lijkt op het eerste gezicht eenvoudig, maar het is wiskundig onmogelijk. Hoe weten we dat? Dankzij een zekere heer genaamd Alan Turing en de beroemde Machine die zijn naam draagt, uit 1936.

Hier komt Tom Scott ons te hulp met zijn uitleg: Stel je een programma voor genaamd "Halts" dat een voorbeeld van elke code kan bekijken en bepalen of het zal stoppen (we hoeven niet te weten hoe het dat doet, het belangrijkste is dat het werkt). Nogmaals: "Halts" ziet de code en antwoordt "ja" (stopt) of "nee" (oneindige lus). Laten we ons nu een tweede programma voorstellen dat verbonden is met "Halts" en precies het tegenovergestelde doet van zijn antwoord. Dus als "Halts" zei dat de code stopt, gaat het tweede programma in een oneindige lus, en als het zei dat het in een lus gaat, stopt het.

Dit systeem wordt "Tegenovergestelde" genoemd, omdat het in wezen het tegenovergestelde doet van wat je erin invoert... maar hier is het punt waarop Turing alles breekt met zijn voorstel: Neem de volledige code waaruit "Tegenovergestelde" bestaat en laat het zichzelf analyseren. Het resultaat... is dat er geen resultaat is. Het is een paradox, een wiskundige onmogelijkheid. Zelfs met de ideale beginvoorwaarden doet een minimale variatie het proces instorten. En daar is ons antwoord op de oorspronkelijke vraag: Er is ten minste één ding dat computers niet en nooit zullen kunnen oplossen.