💬 NLP

Turing or Cantor: That is the Question

Dit paper betoogt dat Alan Turing's werk onlosmakelijk verbonden is met Georg Cantor's theorie, introduceert een maatstaf voor onbeslisbaarheid op basis van inputverdeling, definieert drie nieuwe complexiteitsklassen voor onoplosbare problemen (U-, D- en H-compleet) en bevestigt dat de analoge vraag voor U-compleet negatief is.

Oorspronkelijke auteurs: Eugene Eberbach

Gepubliceerd 2026-04-14

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Eugene Eberbach

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Turing of Cantor: Wie is de ware vader van de computer?

Stel je voor dat je een enorme bibliotheek hebt met alle mogelijke boeken die ooit geschreven kunnen worden. Sommige boeken zijn makkelijk te lezen, andere zijn onbegrijpelijk, en sommige zijn zo raar dat ze eigenlijk geen zin hebben.

Dit artikel, geschreven door Eugene Eberbach, stelt een interessante vraag: Wie heeft de basis gelegd voor onze computers? Is het Alan Turing (de man die de eerste "computer" bedacht) of Georg Cantor (een wiskundige die over oneindigheid droomde)?

De conclusie van het artikel is verrassend: Zonder Cantor had Turing nooit zijn grote doorbraak gehad.

Hier is een simpele uitleg van de belangrijkste punten, met wat creatieve vergelijkingen:

1. De Basis: De Oneindige Bibliotheek (Cantor)

Georg Cantor ontdekte iets gruwelijks (maar fascinerends) in de wiskunde: Er zijn meer getallen dan je kunt tellen.

De analogie: Stel je voor dat je alle natuurlijke getallen (1, 2, 3...) op een rijtje zet. Dat is oneindig, maar je kunt ze allemaal benoemen. Dit noemen we "telpbaar".
Cantor bewees echter dat de reële getallen (alle decimale getallen, zoals $\pi$ of $\sqrt{2}$ ) niet op een rijtje gezet kunnen worden. Er zijn er "meer" oneindig dan er getallen zijn om te tellen. Dit is een "grotere" oneindigheid.

2. De Computer die niet alles kan (Turing)

Alan Turing bedacht een denkbeeldige machine (de Turing-machine) die elke berekening kan doen die een mens met papier en potlood kan doen. Hij wilde bewijzen dat er dingen zijn die nooit opgelost kunnen worden.

De analogie: Turing nam Cantor's idee over. Hij zei: "Stel, elke mogelijke computerprogramma is een getal dat we kunnen tellen (1, 2, 3...). Maar de problemen die we willen oplossen (zoals alle mogelijke wiskundige vragen) zijn als de reële getallen: er zijn er te veel!"
Het resultaat: Omdat er meer problemen zijn dan er computers zijn om ze op te lossen, moeten er per definitie problemen zijn die nooit opgelost kunnen worden. Dit noemen we "onbeslisbaar". Turing gebruikte Cantor's "diagonaalargument" (een slimme truc om te bewijzen dat je lijstje niet compleet is) om dit te bewijzen.

3. Een nieuwe manier om "onoplosbaar" te meten

Tot nu toe dachten we: "Of een probleem is oplosbaar, of het is niet oplosbaar." Dit artikel zegt: "Nee, laten we kijken naar hoe vaak het mislukt."

De analogie: Stel je voor dat je een auto hebt die soms vastloopt in de modder.
- Soms is het pad 100% modder (100% onoplosbaar).
- Soms is het pad 90% modder en 10% asfalt (90% onoplosbaar).
- Soms is het bijna allemaal asfalt (bijna oplosbaar).
  Het artikel stelt voor om te kijken naar de "kans" dat een probleem oplosbaar is, in plaats van alleen te zeggen "nee, het kan niet".

4. Drie nieuwe categorieën voor onoplosbare problemen

Net zoals we in de computerwereld "moeilijke" problemen hebben (zoals het oplossen van een Sudoku die 100 jaar duurt), stelt de auteur drie nieuwe categorieën voor voor problemen die nooit opgelost kunnen worden door een gewone computer:

U-compleet (Universeel compleet):
- De analogie: Dit zijn problemen die we gedeeltelijk kunnen oplossen. Als het antwoord "JA" is, vinden we het misschien wel. Maar als het antwoord "NEE" is, blijft de computer eeuwig nadenken en stopt hij nooit.
- Voorbeeld: De beroemde "Halting Problem" (weet een programma ooit te stoppen?).
D-compleet (Diagonalisatie compleet):
- De analogie: Dit zijn problemen die we helemaal niet kunnen oplossen, zelfs niet als we oneindig lang wachten. Ze zijn zo raar dat ze niet eens op een lijstje met "mogelijke antwoorden" staan.
- Voorbeeld: Het bewijzen dat een bepaalde zin in een taal niet bestaat.
H-compleet (Hypercomputatie compleet):
- De analogie: Dit zijn problemen die zelfs niet opgelost kunnen worden door een supercomputer die oneindig lang werkt. Ze vereisen een heel nieuw soort "magie" of logica die we nog niet hebben.
- Voorbeeld: Problemen die liggen buiten de grenzen van onze huidige wiskunde en logica.

5. De Grootste Les: Er zijn meer vragen dan antwoorden

Het artikel concludeert met een mooi beeld:

Alan Turing gaf ons de gereedschapskist (de computer).
Georg Cantor gaf ons de kaart van de oceaan die laat zien dat er meer water is dan land.

Zonder Cantor's inzicht in de "grotere oneindigheid" had Turing nooit kunnen bewijzen dat computers beperkingen hebben. En dat is eigenlijk een goed ding! Als computers alles konden oplossen, zou de wereld saai zijn. Het feit dat er vragen zijn die we nooit kunnen beantwoorden, houdt de mensheid nieuwsgierig en creatief.

Kortom: Turing bouwde de auto, maar Cantor bouwde de weg die laat zien dat je niet overal kunt komen. En misschien is Cantor wel de "vergeten grootvader" van de informatica.

Titel: Turing of Cantor: Dat is de Vraag

Auteur: Eugene Eberbach (Rensselaer Polytechnic Institute)
Datum: April 2026 (Preprint)

1. Het Probleem

Het artikel adresseert fundamentele vragen binnen de theoretische informatica en de wiskundige logica:

De rol van Cantor: Hoewel Alan Turing wordt erkend als de vader van de informatica, wordt de cruciale invloed van Georg Cantor (op het gebied van verzamelingenleer en de theorie van het oneindige) op Turing's werk vaak onderbelicht. Het artikel stelt dat Turing's bewijzen voor onbeslisbaarheid direct voortvloeien uit Cantor's resultaten.
Beperkingen van de Turingmachine (TM): De traditionele opvatting is dat het bewijzen dat een probleem onoplosbaar is voor een Turingmachine (onbeslisbaar) het einde van het verhaal betekent. Het artikel betoogt dat dit slechts het begin is en dat er een nuance nodig is in het meten van onoplosbaarheid.
Gebrek aan complexiteitsklassen voor onbeslisbare problemen: Bestaande complexiteitstheorie (zoals P, NP, NP-compleet) richt zich op oplosbare maar moeilijk te berekenen problemen. Er ontbreken echter gedefinieerde complexiteitsklassen voor problemen die fundamenteel onoplosbaar zijn door een Turingmachine.
De vraag: Wie heeft meer bijgedragen aan de informatica: Turing of Cantor?

2. Methodologie

De auteur hanteert een theoretische en axiomatische aanpak:

Historische Analyse: Een kritische bestudering van Turing's oorspronkelijke werken (1936, 1939, 1948) en Cantor's verzamelingenleer. De auteur benadrukt dat Turing's bewijs voor het Entscheidungsproblem (beslissingsprobleem) een directe toepassing is van Cantor's diagonaalmethode en de ontelbaarheid van de reële getallen.
Korte Bewijzen: Het presenteren van een verkort bewijs voor de onoplosbaarheid van het Entscheidungsproblem dat puur gebaseerd is op Cantor's theorieën over de kardinaliteit van verzamelingen, in plaats van de traditionele, langere constructies.
Definitie van Nieuwe Concepten: Het introduceren van een "maatstaf voor onbeslisbaarheid" gebaseerd op de waarschijnlijkheidsverdeling van invoerdata (het percentage van onoplosbare instanties versus oplosbare instanties).
Extensie van Modellen: Het uitbreiden van Turing's concept van "Orakel-machines" (o-machines) naar een volledige klasse van Super-Turing (of hypercomputational) modellen.
Classificatie: Het definiëren van nieuwe complexiteitsklassen voor onbeslisbare problemen, geïnspireerd door de Cook/Levin-definitie van NP-compleet.

3. Belangrijkste Bijdragen

A. De Relatie tussen Cantor en Turing

De auteur concludeert dat Turing's prestaties niet mogelijk waren geweest zonder Cantor's werk.

Turing associeerde het aantal Turingmachines met de natuurlijke getallen (aftelbaar).
Hij associeerde het aantal talen/problemen met de reële getallen (onaftelbaar).
Omdat de reële getallen strikt groter zijn dan de natuurlijke getallen (Cantor), moeten er problemen bestaan die niet door Turingmachines kunnen worden opgelost. De auteur stelt dat Cantor de "vergeten grootvader" van de informatica is.

B. Nieuwe Maatstaf voor Onoplosbaarheid

In plaats van een binair "oplosbaar/onoplosbaar" oordeel, stelt de auteur voor om de graad van onoplosbaarheid te meten op basis van de invoerdata:

0% onoplosbaarheid: Recursieve talen (altijd oplosbaar).
100% onoplosbaarheid: Alle instanties zijn onoplosbaar.
Tussenliggende waarden: Probleeminstanties kunnen worden benaderd of gedeeltelijk opgelost op basis van de waarschijnlijkheidsverdeling van de invoer.

C. Drie Nieuwe Complexiteitsklassen voor Onbeslisbare Problemen

De auteur introduceert drie nieuwe klassen, geordend op basis van toenemende "hardheid" van onoplosbaarheid:

U-compleet (Universal Complete):
- Definitie: Talen die semi-beslisbaar zijn (recursively enumerable maar niet recursief). Als een woord in de taal zit, kan dit in eindige tijd worden bevestigd; als het er niet in zit, loopt de machine oneindig door.
- Voorbeelden: Het taal van de Universele Turingmachine ( $L_u$ ), Post's Correspondence Problem (PCP), het Busy Beaver-probleem.
- Relatie: Deze klasse komt overeen met $RE \setminus REC$ . Het is de "eenvoudigste" vorm van onoplosbaarheid.
- Resultaat: Bewezen dat recursieve talen ($REC$) niet gelijk zijn aan recursief oplosbare maar niet-recursieve talen voor U-compleet problemen.
D-compleet (Diagonalization Complete):
- Definitie: Talen die niet eens semi-beslisbaar zijn. Geen enkele Turingmachine kan de leden van deze taal accepteren.
- Voorbeelden: De diagonaaltalen ( $L_d$ ), de complementen van U-compleet talen.
- Relatie: Deze klasse valt onder de niet-recursief oplosbare talen (non-RE).
H-compleet (Hypercomputation Complete):
- Definitie: Talen die zelfs niet beslisbaar zijn met oneindige stappen (hyper-onbeslisbaar). Ze vereisen hypercomputatie (bijv. orakels van een hoger niveau) om opgelost te worden.
- Voorbeelden: Hyper-diagonaaltalen ( $L_{hd}$ ).
- Relatie: Deze klasse vereist modellen die verder gaan dan zelfs oneindige Turingmachines (bijv. machines met oneindige orakels).

D. Uitbreiding naar Super-Turing Modellen

Het artikel breidt Turing's concept van o-machines (orakel-machines) uit tot een hiërarchie van hypercomputatie. Net zoals Cantor een oneindige hiërarchie van kardinaliteiten introduceerde, stelt de auteur een oneindige hiërarchie van complexiteitsklassen voor onbeslisbare problemen voor, gebaseerd op de kracht van de orakels.

4. Resultaten

Bewijs van Onoplosbaarheid: Een korter, meer direct bewijs voor het Entscheidungsproblem dat puur steunt op Cantor's diagonaalmethode en de ontafelbaarheid van de reële getallen.
Negatief antwoord op een analogie van P vs NP: Voor de klasse van U-compleet problemen is het bewezen dat $REC \neq RE$ . Dit betekent dat er geen algoritme bestaat dat alle U-compleet problemen in eindige tijd kan oplossen, zelfs niet met gokken (in tegenstelling tot de open vraag of $P=NP$ voor oplosbare problemen).
Hiërarchie: Het aantonen dat er een oneindige hiërarchie van complexiteitsklassen bestaat voor onbeslisbare problemen, geïnspireerd door Cantor's theorie van ordinaalgetallen en kardinaliteiten.
Kardinaliteit: Het bevestigen dat er meer onoplosbare problemen zijn (kardinaliteit van de reële getallen) dan oplosbare problemen (kardinaliteit van de natuurlijke getallen).

5. Betekenis en Conclusie

Paradigmaverschuiving: Het artikel daagt de traditionele opvatting uit dat onbeslisbaarheid het einde van onderzoek betekent. In plaats daarvan stelt het voor om onbeslisbare problemen te benaderen via waarschijnlijkheid, benadering en super-Turing modellen.
Erkenning van Cantor: Het artikel pleit ervoor Georg Cantor te erkennen als een fundamentele grondlegger van de informatica, naast Turing, Church en Gödel. Zonder Cantor's inzichten in het oneindige zou Turing's bewijs voor de beperkingen van algoritmen niet mogelijk zijn geweest.
Toekomstgericht: De introductie van U-, D- en H-compleet klassen biedt een raamwerk voor het classificeren van problemen die buiten het bereik van klassieke computers vallen, wat relevant is voor de ontwikkeling van hypercomputatie, kunstmatige intelligentie en complexe systemen.
Conclusie: De titelvraag "Turing of Cantor?" wordt beantwoord met de stelling dat Cantor de theoretische basis leverde (de "grootvader"), terwijl Turing de architect was die deze basis gebruikte om de fundamenten van de moderne informatica te bouwen. De auteur concludeert dat de informatica paradoxaal genoeg de meeste inspanning steekt in "makkelijke" oplosbare problemen, terwijl de overgrote meerderheid van de wiskundige problemen onoplosbaar is.