Het begin van moderne computerwetenschap

Vhier zullen we het hebben over het paradoxale begin van moderne Informatica. En ik zeg paradoxaal, omdat het niet ontstond toen men een efficiënte manier zocht om rekeningen uit te voeren, maar toen men probeerde aan te tonen dat er problemen waren die niet berekbaar waren.

De held van dit verhaal is een man genaamd Alan Turing, die al een personage was in een Hollywood-film getiteld "The Imitation Game"Het spel van imitatieen heeft een Turing-prijs voor informatica, die jaarlijks wordt uitgereikt aan een onderzoeker die zich heeft onderscheiden op het gebied. In 1937 toonde hij wiskundig aan dat er problemen zijn die niet berekbaar zijn. Om dit te doen, moest hij echter definiëren wat "berekbaar" betekent, en in dat proces creëerde hij de Turingmachines. Deze machines zijn abstracte wiskundige concepten die het concept van berekening formaliseren, en een belangrijk wiskundig resultaat dat hij ontdekte toont aan dat er een speciale machine bestaat, genaamd de Universele Turingmachine, die een centrale rol speelt in de Theorie van de Berekening. Deze Universele Turingmachine is de basis voor de constructie van de computers zoals we ze vandaag kennen.

Het eerste artikel van Turing heeft een aantal dingen die opvallen en die aanwezig zijn in de titel van het artikel, hier vrij vertaald:Over berekbare getallen en een toepassing op het beslissingsprobleemWat bedoel je met berekbare getallen? Betekent dat dat er niet-berekbare getallen bestaan?

Ja, en dat is niet zo moeilijk te zien. Maar eerst, laten we even terug in de tijd, want de vroege ontwikkeling van de berekening is nauw verbonden met oneindige getallen. In 1874 publiceerde de Duitse wiskundige Georg Cantor een artikel waarin hij aangaf dat er meer dan één soort oneindigheid bestaat. In het bijzonder toonde hij aan dat het oneindige van de natuurlijke getallen 0,1,2,3... kleiner is dan het oneindige van de reële getallen. Misschien heb je dit al eens opgemerkt, vanuit een eenvoudige tekening. Het oneindige van de reële getallen correspondeert aan een continue lijn (dit verzameling wordt de Continue genoemd), en op die lijn kunnen we de natuurlijke getallen of de gehele getallen op een behoorlijk afstand van elkaar plaatsen (de grootte van dit andere oneindige wordt de Aantelbare genoemd). Met een zeer innovatieve strategie toonde Cantor aan dat het niet mogelijk is om de elementen van de Continue één voor één uit te lijnen met de Aantelbare, er blijft altijd een getal over dat niet uitgelijnd wordt. Op deze manier toonde hij aan dat de Continue strikt groter is dan de Aantelbare.

Dus komt Turing, die aantoont dat er reële getallen bestaan die niet berekbaar zijn. Niet berekbare getallen zijn altijd elementen van het Continuüm. Volgens zijn definitie is een reëel getal berekbaar als er een programma of, in de originele versie, een Turingmachine bestaat die oneindig veel van zijn cijfers afdrukt. Maar elk programma en elke Turingmachine heeft een eindige grootte en wordt opgeslagen in een bestand. Een bestand is niets meer dan een natuurlijk getal, dat wel groot kan zijn. Dus het maximale aantal programma's is een meetbaar oneindig, en er kunnen niet genoeg programma's zijn om alle reële getallen af te drukken. Veel reële getallen kunnen niet worden afgedrukt door een enkel programma, en dit zijn de niet-berekbare reële getallen. En nu weten we dat de meeste reële getallen niet berekbaar zijn, slechts een klein percentage ervan kan worden afgedrukt door een programma of een Turingmachine.

Een klein geflirt hier. Toen Turing in 1936 zijn artikel schreef, had hij zonder zijn kennis al een andere beroemde wiskundige, Alonzo Church, laten zien dat er niet-berekbare getallen bestaan, met behulp van heel andere technieken. Dus de redacteuren van het tijdschrift waren twijfelachtig of het artikel van Turing echt origineel was. Het artikel bleef op een tafel staan totdat iemand het idee had om dit artikel aan Church zelf te laten zien, die het idee van Turing zo origineel vond dat hij hem uitnodigde om zijn doctoraat in de Verenigde Staten te volgen. Door deze vertraging werd het artikel pas in 1937 gepubliceerd. Turing voltooide zijn doctoraat in een jaar en keerde terug naar Engeland toen de Tweede Wereldoorlog uitbrak. Daar begint het verhaal van de film.Het spel van imitatie, nadat Turing al een groot bijdrage had geleverd aan de geschiedenis van de moderne informatica.

Terug naar de getallen, de eerste reactie van mensen wanneer ze leren dat er niet-berekbare getallen bestaan, is als volgt: "Toon me alsjeblieft een voorbeeld van een niet-berekbaar getal". En ik, met plezier, antwoord: "Ik kan dat niet laten zien. Als ik het getal laat zien, dan heb ik het al berekbaar gemaakt. En een niet-berekbaar getal kan niet worden berekbaar gemaakt. Logisch, toch? Nou, als dat niet logisch is, dan moet je je eraan wennen dat je nooit een niet-berekbaar getal zult zien, precies omdat het niet berekbaar is."

Maar, als het getal niet te berekenen is, hoe dan? We moeten dan indirecte manieren gebruiken om het getal te definiëren, zonder enige berekening. Een bekend voorbeeld is "de kans dat een computerprogramma stopt". Deze uitdrukking tussen aanhalingstekens is de definitie van het getal. Het wordt aangetoond dat dit een niet-berekenbaar getal is waarvan we bijna niets kunnen weten. Het is niet mogelijk om te weten of dit getal kleiner is dan 0,5 of groter dan 0,00000001. Alle deze vragen zijn ook niet-berekenbare vragen.

En dit brengt ons terug naar het oorspronkelijke artikel van Alan Turing. Hij toonde aan dat er problemen zijn die niet berekenbaar zijn, ofwel dat ze niet door een Turing-machine kunnen worden berekend, inclusief dat bekende Probleem van de Beslissing (van de eerste orde logica) dat in de titel van zijn artikel stond.

En zo ontstond de moderne computerwetenschap, die toonde dat de computerwetenschap grenzen heeft. Er zijn dingen die nooit kunnen worden berekend, en we moeten leven binnen de grenzen van wat met een computer mogelijk is. Het Turing-stadium is onafhankelijk van elke programmeertaal en elk type computer. Daarom blijven de niet-berekenbare problemen niet-berekenbaar, ongeacht welke technologie, zelfs de meest geavanceerde kunstmatige intelligentie of technologieën die in de toekomst worden uitgevonden.

________________
(De meningen die in de artikelen gepubliceerd zijn inDe USP-krantDeze zijn volledig de verantwoordelijkheid van de auteurs en weerspiegelen geen meningen van het medium of institutionele standpunten van de Universiteit van São Paulo. Bezoek hier onzeredactionele richtlijnen voor opiniestukken.)