Operationaliteitꜛ
Ik kan de inhoud van een boek met de complete werken van Vondel weliswaar samenvatten in één zin, „De werken van Vondel”, maar die zin op zich bevat niet voldoende informatie om het boek te produceren. Het is alsof we tegen een beginnend schaker zeggen „Houd druk op de linkerflank” — iemand moet al een grote hoeveelheid kennis van het schaakspel hebben om iets met die zin te kunnen. Evenzo kan enkel iemand die de werken van Vondel al kent uit de beschrijving „De werken van Vondel” het originele boek reproduceren.
We eisen daarom dat een beschrijving (of verklaring) operationeel is, dat is: uitvoerbaar is zonder bijzondere voorkennis. En om dat nog stricter te maken stellen we dat een beschrijving operationeel is als zij mechanisch kan worden uitgevoerd, bijvoorbeeld door een computer die weliswaar arbitrair veel tijd en geheugenruimte mag gebruiken, maar slechts een eindige hoeveelheid informatie vooraf heeft (bijvoorbeeld kennis van een computertaal).
Een technisch detail.
In de ene computertaal is een beschrijving vaak veel korter of langer dan in de andere. Maakt dit bovenstaande definitie van informatie-inhoud niet zinloos? Neen, want de meeste computertalen zijn universeel. Een universele taalꜛ is een taal waarin de werking van iedere andere computertaal kan worden beschreven. Stel dat iemand een beschrijving „Doe zus” in taal A geeft, dan is die beschrijving direct om te zetten naar taal B: „Voer <beschrijving van A> uit met als invoer: Doe zus”. Deze zin is maar een eindig, vast stuk groter dan de oorspronkelijke zin, dus de lengten van beschrijvingen in verschillende talen verschillen hooguit een constante.
Dit is niet wezenlijk anders dan bij natuurlijke talen. Als een grammatica plus woordenboek een goede beschrijving van een taal geven, kan ik aan iemand die geen Frans kent de opdracht geven: „Leer de taal die in deze boeken beschreven staat, en voer daarna de volgende, in die taal gestelde, opdracht uit”, met daarachter een arbitraire opdracht in het Frans. Het zal vast een stuk langer duren dan het uitvoeren van diezelfde opdracht in de moedertaal, maar uiteindelijk zou het resultaat hetzelfde moeten zijn als wanneer die persoon wel Franstalig was geweest.
In computertermen: we kunnen altijd een (compilerꜛ of) interpreterꜛ voor A schrijven in B, en door die interpreter, een vast stuk tekst, toe te voegen aan de beschrijving-in-A krijgen we een beschrijving-in-B.
(In de praktijk zijn er natuurlijk bijna altijd kortere beschrijvingen-in-B, maar bovenstaande redenering bewijst dat er in ieder geval één bestaat die niet meer dan een een constante langer is dan de beschrijving-in-A, en dat is genoeg voor onze theorie. Dat is het zogeheten theeketeltjesbeginselꜛ, naar het volgende verhaal.
Een wiskundige overnachtte in een oud, verder leegstaand huis, en had zin in thee. Er was genoeg thee, en ook kopjes en een werkend fornuis, maar een theeketeltje was zo gauw niet te vinden. De wiskundige doorzocht het hele huis en de tuin, en meende uiteindelijk beneden in de oude waterput iets te zien. Met veel moeite daalde hij aan de roestige ketting af, en vond inderdaad een oud, gehavend theeketeltje. Met nog meer moeite klom hij weer omhoog, en begon aan het lastige karwei de gaten in het keteltje te lappen met de materialen die hij had. Hij smolt wat tinnen lepels, en met behulp daarvan lukte het hem uiteindelijk stukken van een gevonden conservenblikje op de gaten te solderen, en zo kon hij uiteindelijk water koken en thee zetten. (Vraag tussendoor: hoe kwam het dat het tin niet smolt bij het water koken?)De volgende avond had hij weer zin in thee, dus hij pakte het theeketeltje, sloeg er wat gaten in, en wierp het in de waterput. „Ziezo, probleem gereduceerd tot een al eerder opgelost probleem!”)
((Te doen.))
Traditioneel wordt operationaliteit bewezen door het geven van een programma voor een Turingmachineꜛ.