TOPIC 12: Beperkingen aan Berekenbaarheid¶

We hebben reeds een heleboel interessante vraagstukken opgelost m.b.v. Python. We kunnen ons nu echter de vraag stellen of werkelijk ieder (wetenschappelijk geformuleerd) vraagstuk uit te rekenen valt in Python. Zoals we zullen zien heeft het antwoord op deze vraag niets te maken met Python. Er zijn talloze programmeertalen en het blijkt dat die vanuit fundamenteel wetenschappelijk oogpunt bekeken allemaal precies even krachtig zijn: een computationeel vraagstuk dat oplosbaar is in Python, is ook oplosbaar in andere programmeertalen, en omgekeerd. Men zegt dat al deze programmeertalen Turing-compleet zijn (ter ere van Alan Turing, één van de vaders van de computerwetenschappen). De keuze voor een bepaalde programmeertaal heeft dan ook niets met kracht maar alles met programmeerstijl te maken. Sommige talen zijn goed geschikt om zeer laag-niveau technische problemen op te lossen. Andere talen zijn dan weer beter geschikt om zeer hoog-niveau wetenschappelijke problemen in uit te drukken.

Indien de programmeertaal er eigenlijk niet toe doet, wordt de vraag die we ons dan eigenlijk moeten stellen de volgende: is ieder (wetenschappelijk formuleerbaar) vraagstuk überhaupt oplosbaar met een computer? Dat blijkt niet zo te zijn en we zullen dit formeel bewijzen.

De tak van de computerwetenschappen die zich bezighoudt met de fundamentele mogelijkheden en beperkingen van computers noemt men de theoretische informatica. Het is een tak van de computerwetenschappen die de wiskundige taal gebruikt (t.t.z. kwantoren zoals \(\forall\) en \(\exists\), definities, stellingen, etc) maar die deze taal gebruikt om precies te redeneren over computers, programma’s, inputs, enz. i.p.v. getallen, integralen, afgeleiden, enz. De redeneringen die we in de theoretische informatica opstellen zijn dus puur conceptueel en maken totale abstractie van alle technologische aspecten die gepaard gaan met computerwetenschappen. Ze zijn dus onafhankelijk van de (razendsnel evoluerende) software- en hardwaretechnologie. Ze zijn dus universeel geldig.

In dit hoofdstuk bestuderen we dus een reeks fundamentele beperkingen van computers. Omwille van de onafhankelijkheid van programmeertalen of hardwaretechnologieëen, spreekt men dan ook van beperkingen aan berekenbaarheid. Het gedeelte van de theoretische informatica dat zich bezig houdt met de fundamentele beperkingen van berekenbaarheid, noemt men berekenbaarheidstheorie. Een gedegen inleiding tot de berekenbaarheidstheorie vereist minstens een cursus van een volledig semester, niet in het minst omdat alle begrippen precies en formeel dienen te worden gedefinieerd. Bovendien moeten voor vele stellingen tussenresultaten worden bewezen in de vorm van hulpstellingen. Aangezien we in deze cursus hiervoor niet de tijd en ruimte hebben, maar we je toch willen laten inzien wat de fundamentele beperkingen van computers zijn, zullen we ons beperken tot informele schetsen van de gegeven bewijzen. We laten dus wel de redenering zien achter ieder resultaat, zonder helemaal diep in te gaan op alle technische details van iedere stelling.

Niet Alles is Berekenbaar¶

We vallen meteen met de deur in huis: niet alles is berekenbaar met een computer! Laat ons even toespitsen op eenvoudige functies \(f: \mathbb{N} \rightarrow \mathbb{N}\). Men zou op het eerste zicht op z’n minst verwachten dat zulke functies programmeerbaar zijn in Python. We hebben immers reeds een pak zulke functies (zoals bvb. square) geprogrammeerd. Het blijkt echter dat lang niet alle functies van \(\mathbb{N}\) naar \(\mathbb{N}\) in Python uitrekenbaar zijn. Om dat te bewijzen moeten we dus aantonen dat er voor zekere functies geen programma bestaat in Python. Dit kunnen we het makkelijkste doen door een contradictie af te leiden indien we aannemen dat alle functies toch programmeerbaar zijn in Python.

Niet alle functies \(f: \mathbb{N} \rightarrow \mathbb{N}\) zijn programmeerbaar in Python.

Stel dus uit het ongerijmde, dat alle functies \(f: \mathbb{N} \rightarrow \mathbb{N}\) programmeerbaar zijn in Python. We stellen dus dat er voor ieder zulke functie \(f\) een Python programma p bestaat dat \(f\) berekent.

Laat ons even alle zulke Python programma’s in beschouwing nemen. Ieder Python programma is in feite slechts een string van karakters. Sommige Python programma’s zijn zeer kort; andere zijn dan weer zeer lang. Conceptueel kunnen we dus een oneindig lange rij van Python programma’s beschouwen die (a) allemaal functies van \(\mathbb{N}\) naar \(\mathbb{N}\) uitrekenen, en die (b) gesorteerd zijn op lengte: de korte programma’s staan vooraan en de langere programma’s staan steeds na de kortere. We nummeren deze programma’s: p0, p1, p2, ….

We tonen nu aan dat niet alle functies \(f: \mathbb{N} \rightarrow \mathbb{N}\) in deze rij voorkomen. Stel van wel. Dan moet er dus een rij van functies bestaan \(f_0\), \(f_1\), \(f_2\) die precies overeenkomt met de rij van programma’s (t.t.z. zodat pi een programma is voor \(f_i\)). Bekijk nu volgende functie:

\[g(k) = f_k(k)+1\]

\(g\) is overduidelijk een functie van \(\mathbb{N}\) naar \(\mathbb{N}\). Ook deze functie moet dus in het rijtje voorkomen want we namen aan dat het rijtje alle functies bevat. M.a.w. \(\exists M : g = f_M\).

Maar dan hebben we \(g(M) = f_M(M)\) maar ook \(g(M) = f_M(M)+1\) wegens de definitie van \(g\). Dat is duidelijk een contractie. De enige aanname die we gemaakt hebben is dat alle functies berekenbaar zijn. Dat kan dus niet het geval zijn.

Opmerking 1 Merk op dat we in het bovenstaande bewijs nergens gebruik gemaakt hebben van het feit dat we Python gebruiken. Het bewijs geldt voor alle programmeertalen en steunt in feite enkel op het feit dat programma’s eindig lange strings zijn en we dus conceptueel aan een gesorteerde rij van programma’s kunnen denken. Vermits programma’s in gelijk welke programmeertaal eindig lange strings zijn (die aan bepaalde regels — bvb. syntaxregels — voldoen), geldt het argument voor iedere programmeertaal.

Opmerking 2 Voor de meer wiskundig georiënteerde student merken we nog op dat het overgrote deel van de functies van \(\mathbb{N}\) naar \(\mathbb{N}\) niet berekenbaar zijn. We hebben eigenlijk gesteund op het feit dat de verzameling \(\{f~|~ f: \mathbb{N} \rightarrow \mathbb{N} \}\) een overaftelbare verzameling is, terwijl de oneindige rij van programma’s duidelijk aftelbaar is. Er zijn dus evenveel programma’s als er natuurlijke getallen zijn. Er zijn echter evenveel functies van \(\mathbb{N}\) naar \(\mathbb{N}\) als er reëele getallen zijn!

Het Halting Probleem¶

Indien we ons dus beperken tot functies van \(\mathbb{N}\) naar \(\mathbb{N}\) blijkt het leeuwendeel al niet uitrekenbaar met een computer. Indien we onze probleemstelling verruimen naar vraagstukken die gaan over “rijkere” data dan natuurlijke getallen, wordt de zaak alleen maar erger.

Maar zijn de onberekenbare vraagstukken werkelijk interessante vraagstukken, of gaat het hem hier slechts over een theoretische snuisterij? Helaas is dat niet het geval. Beschouw het volgende stukje Python code:

def f(x):
    while (x>0):
        x = x + 1
        
f(4)

Indien we dit stukje code uitvoeren krijgen we duidelijk een oneindige lus. In dit geval is dat vrij triviaal aangezien de body van de while de waarde van x altijd maar groter maakt en de voorwaarde om de while lus nog een keer uit te voeren dus steeds voldaan blijft. Helaas is het bijlange niet altijd zo makkelijk te zien of een gegeven stuk code al dan niet in een oneindige lus verzeild zal raken. De kans is groot dat je in de oefeningenlessen reeds zelf te maken hebt gehad met een stukje code dat abusievelijk resulteert in een oneindige lus of in een oneindige recursiediepte. Het zou dan ook zeer handig zijn moest een programmeeromgeving ons vóór de uitvoering van onze code hierover kunnen verwittigen.

Merk op dat ook “serieuze applicaties” soms in een oneindige lus geraken. In de figuur hieronder zien we een screenshot van de “task manager” op een Apple computer. Het venstertje vertelt ons dat er momenteel \(5\) applicaties open zijn maar dat de applicatie “Firefox” kennelijk al een tijdje niet meer heeft gerapporteerd aan de task manager. We kunnen op dit moment alleen maar raden naar het feit of Firefox al dan niet in een oneindige lus verzeild is. Misschien is de applicatie druk bezig met een zeer zware berekening en zal ze zo meteen rapporteren dat ze nog responsief is. Ook hier zou het weer handig zijn indien iets of iemand de makers van Firefox op voorhand zou kunnen garanderen dat Firefox nooit in een oneindige lus zal geraken. Met deze garantie op zak zouden we nu zeker zijn dat Firefox iets nuttig aan het doen is en zo meteen weer responsief zal worden.

Beide voorbeelden tonen aan dat het interessant zou zijn om -gegeven een stuk code- met zekerheid te kunnen zeggen of die code, indien we ze uitvoeren, al dan niet in oneindige lus zal resulteren. Bovendien zouden we dit door onze computer moeten kunnen laten verifiëren!

Programma’s over Programma’s¶

Tot nu toe hebben we ons beperkt tot het schrijven van programma’s die getallen, strings, booleans, tupels, lijsten, objecten, enz. als invoer nemen. Er bestaan echter ook programma’s die programma’s als invoer kunnen nemen. Het meest eenvoudige voorbeeld hiervan is de kernel van een programmeertaal. De Python kernel, die met deze notebook geïntegreerd is, is een programma (geschreven in de programmeertaal C) dat jouw programma’s uitvoert. Het is dus een programma dat programma’s als invoer neemt. Andere voorbeelden in hetzelfde genre zijn Mathematica, Matlab en Excel. Deze programma’s nemen programma’s (weliswaar geschreven in een andere taal dan Python) als invoer en voeren die programma’s uit. Minder gekende voorbeelden zijn Safari, Internet Explorer, Firefox en Chrome. Deze internetbrowsers laden een pagina van het internet en tonen deze op je scherm. Indien je de menu-optie “View Source” kiest in één van deze programma’s zie je dat een webpagina eigenlijk een programma is dat beschrijft hoe die webpagina zich in je browser dient te gedragen. De meest gebruikte taal om webpagina’s te “programmeren” vandaag is JavaScript. Een internetbrowser is dus eigenlijk ook een programma dat een programma (geladen van het internet) als invoer neemt.

Dit zijn slechts enkele voorbeelden die aantonen dat programma’s ook kunnen opereren over programma’s. Die input-programma’s kunnen we bij voorbeeld als een string voorstellen. We weten immers dat een programma slechts een stuk tekst is geschreven in één of andere programmeertaal.

Terug naar het Halting Probleem¶

Laat ons nu terugkeren naar de vraag of we een computer kunnen laten verifiëren of een gegeven programma in een oneindige lus zal gaan of niet. Wat we dus zouden willen, is een (Python) programma halt waarvan de hoofding er ongeveer als volgt uitziet:

def halt(prog, input):
    # prog en input zijn strings
    # halt geeft True terug als en slechts als prog stopt op de input
    ...

De bedoeling is dus dat we halt kunnen laten checken of prog zou stoppen op de invoer input zonder uiteraard prog(input) effectief uit te voeren (want dan is het te laat indien dat inderdaad in een oneindige lus resulteert!). We zouden dus graag het volgende kunnen doen:

halt("f(x): while x>0: x=x", "4")

halt("fac(x): if x==0: return 1 else: return x*fac(x-1)","4")

Helaas is dit onmogelijk.

halt bestaat niet.

Stel dat halt wel bestaat. Schrijf dan het volgende programma:

def self_halt(prog):
    if halt(prog,prog):
        while True:
            pass  # doe niks interessants

Het (lichtjes rare) programma self_halt neemt 1 programma en kijkt m.b.v. halt na of dat programma stopt indien we het op zichzelf los laten. Laten we dan nu eens self_halt op zichzelf loslaten, t.t.z. we beschouwen self_halt(self_halt).

Ofwel stopt self_halt(self_halt). Kijkend naar de code, is dat alleen mogelijk indien de oneindige lus niet bereikt wordt, wat alleen mogelijk is als halt(self_halt,self_halt) gelijk is aan False. Maar dit betekent dat self_halt niet stopt op self_halt. Een contradictie!
Ofwel stopt self_halt(self_halt) niet. Dat is alleen mogelijk indien self_halt in de oneindige while lus is geraakt. Maar dan was halt(self_halt,self_halt) gelijk aan True wat betekent dat self_halt stopt op self_halt. Opnieuw een contradictie!

Deze (toegegeven, vergezochte) redenering is helemaal correct. De enige fout die we begaan kunnen hebben is het aannemen dat halt effectief bestaat. Dat is hierbij dus een formeel bewezen onmogelijkheid.

Een Variante: Delen door Nul¶

Het slechte nieuws stopt hier echter niet. Beschouw bijvoorbeeld de eigenschap “delen door nul”. Sommige programma’s zullen correct zijn en nooit een deling door nul uitvoeren. Andere programma’s bevatten een programmeerfout en zullen ooit eens delen door nul. Het zou handig zijn indien we dat (door een verfieer-programma) zouden kunnen laten checken zonder het programma uit te voeren.

De vraag is dus of het volgende programma überhaupt bestaat:

def divides_by_zero(prog):
    # prog is een programma
    # we geven True terug asa prog ergens iets/0 doet
    ...

Helaas. Ook divides_by_zero kan onmogelijk bestaan.

Stel dat divides_by_zero tóch bestaat. Dan kunnen we op basis hiervan ook het volgende speciale programma schrijven:

def speciaal(prog, input):
    def f():
        prog(input)
        return 1/0
    return divides_by_zero(f)

Dit betekent dat speciaal(prog, input) True oplevert als en slechts als divides_by_zero(f) True oplevert. Maar dit is alleen mogelijk als en slechts als prog(input) stopt (anders wordt return 1/0 nooit bereikt), t.t.z. als en slechts als prog stopt op input.

Dit zou echter betekenen dat speciaal precies het hierboven gezochte programma halt is. En dat is onmogelijk. De enige fout in onze redenering is dat we hebben aangenomen dat divides_by_zero bestaat.

Veralgemening: De Stelling van Rice¶

We hebben dus al twee voorbeelden gezien van nuttige uitspraken over programma’s die we niet door een computer kunnen laten verifiëren.

De situatie is echter nog veel dramatischer. De vragen “stopt een programma of niet” en “zal het programma ooit door nul delen of niet” zijn slechts twee voorbeelden van vragen die we ons kunnen stellen over de uitvoering van programma’s. De volgende stelling veralgemeent het slechte nieuws tot alle mogelijke eigenschappen over de uitvoering van programma’s.

Geen enkele eigenschap over de uitvoering van programma’s is verifieerbaar m.b.v. een programma.

Kies een willekeurige eigenschap over de uitvoering van programma’s (bvb: print het ooit \(5\) af of niet). Stel dat er een programma bestaat dat kan nakijken of programma’s aan deze eigenschap voldoen of niet:

def eigenschap(prog):
    # prog is een programma
    # we geven True terug asa de eigenschap waar is 
    ...

Indien dit programma bestaat, dan kunnen we ook het volgende programma bouwen (de redenering is helemaal dezelfde als hierboven):

def speciaal(prog, input):
    def f():
        prog(input)
        een-expressie-met-de-eigenschap-waar
    return eigenschap(f)

Dit betekent dat speciaal(prog, input) True oplevert als en slechts als eigenschap(f) True oplevert. Maar dit is alleen mogelijk als en slechts als prog(input) stopt, t.t.z. als en slechts als prog stopt op input.

Dit betekent opnieuw dat speciaal precies het hierboven gezochte programma halt is. Nogmaals, dat is onmogelijk. eigenschap bestaat dus niet.

Samenvatting¶

In dit korte topic hebben we laten zien dat er fundamentele beperkingen zijn aan wat met computers mogelijk is. De redeneringen die we hebben gemaakt zijn onafhankelijk van Python en gelden voor gelijk welke programmeertaal.

We eindigen dit topic met een filosofische noot: zijn wij mensen wél in staat om bovenstaande problemen op te lossen? Zijn wij bijvoorbeeld “slim genoeg” om van ieder programma te bepalen (zonder het uit te voeren) of het stopt of niet? Kunnen wij van gelijk welk programma bepalen of het deelt door nul? Enzovoort. Sommige wetenschappers zijn van oordeel dat dat inderdaad het geval is. Anderen zijn van het tegendeel overtuigd en gaan er van uit dat wij slechts (weliswaar zeer intelligent geprogrammeerde) computers zijn.

De tak van de computerwetenschappen die probeert van menselijke intelligentie m.b.v. computers te simuleren noemt met artificiële intelligentie (of kortweg AI). De eerste groep wetenschappers is dus van mening dat AI nooit zal werken: er zijn immers steeds interessante dingen die mensen kunnen en computers niet. De tweede groep denkt dat het een kwestie is van tijd en dat er dus ooit wel een programma kan geschreven worden dat precies hetzelfde kan als wij.

Inleiding tot de Computerwetenschappen