[De theorie van berekening] probeert te begrijpen waarom, en op welke manier, sommige problemen gemakkelijk zijn, en andere moeilijk. Dit gaat niet over hoe snel onze computers zijn, evenmin als astronomie de studie van telescopen is. Dit gaat over de wiskundige structuur van problemen, en hoe deze structuren ons helpen om de problemen op te lossen, of juist in de weg zitten om tot een oplossing te komen. Dit, op zijn beurt, leidt tot vragen over de wiskundige bewijsbaarheid, en zelfs over intelligentie en creativiteit.
-- Christopher Moore and Stephan Mertens - "The Nature of Computation" (2011)
De grondslagen van berekenbaarheidstheorie (computability theory) werden gelegd in de jaren 1930, door onder andere Alonzo Church, John Barkley Rosser, Stephen Kleene en vooral Alan Turing, wiens 100ste geboortejaar in 2012 gevierd wordt als het Alan Turing Year. Zij realiseerden zich dat het mogelijk is om het intuïtieve begrip van "berekening" in een robuuste wiskundige definitie te gieten, onafhankelijk van welke hardware of programmeertaal er ook gebruikt wordt om de berekening te verwezenlijken. Hiermee kon men beginnen te bouwen aan een theorie van berekenbare en onberekenbare verzamelingen en functies. En de berekenbaarheidstheorie kijkt meestal meer naar het onberekenbare dan naar het berekenbare. Inderdaad: zodra je weet dat een iets berekenbaar is, is het vooral nog interessant voor informatici, die de efficiëntie en het geheugengebruik zullen besturen van de algoritmes die het probleem oplossen. Berekenbaarheidstheoristen zijn echter niet zo geïnteresseerd in efficiëntie en geheugengebruik. Zij onderzoeken liever de rijke en elegantie theorie van onberekenbare functies. Zo houdt het bijvoorbeeld niet op bij het begrip onberekenbaarheid; men kan verschillende graden van onberekenbaarheid definiëren, waarbij de ene onberekenbare functie verder van berekenbaarheid kan zijn dan de andere.
Zelfs bestudeer ik vooral algorithmic randomness, een deelgebied van de berekenbaarheidstheorie. Randomness wordt hier gebruikt in een andere betekenis dan in de statistiek. In de statistiek spreekt men over stochastische variabelen en processen, maar men heeft geen begrip van randomness voor een rij van uitkomsten. Beschouw bijvoorbeeld het herhaaldelijk opwerpen van een eerlijke munt, waarbij we de uitkomst "kop" als 0 en de uitkomst "munt" als 1 noteren. Twee mogelijk rijen van uitkomsten zijn:
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1...
en
0 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 1 1...
Voor de statisticus zijn deze twee rijen even waarschijnlijk. We zien echter onmiddellijk dat de eerste rij er heel regelmatig (niet-random) uitziet, terwijl de tweede rij wel vrij random lijkt. Algorithmic randomness biedt een oplossing voor deze paradox. In algorithmic randomness gebruikt men berekenbaarheidstheorie om te definiëren wat men juist als regelmatigheid in zulk een rij kan beschouwen, en welke rijen werkelijk random zijn.
Merk op dat randomness veel sterker is dan onberekenbaarheid. Je kan gemakkelijk een rij construeren waarvan de bits met oneven posities onberekenbaar zijn, terwijl er op de even posities steeds een 0 staat, wat een heel sterke regelmatigheid is, zodat de rij zeker niet random kan zijn.
Door de vele subtiele manieren waarin een rij een regelmatigheid kan hebben, duurde het tot in de jaren 1960 eer de eerste degelijke definitie van algorithmic randomness werd gegeven, door Per Martin-Löf. In de daaropvolgende decennia werden er veel nieuwe definities voorgesteld, vanuit zeer verschillende invalshoeken, zoals maattheorie, martingales, Kolmogorov-complexiteit, berekenbare analyse en ergodische theorie. Sommige benaderingen leidden tot equivalentie definities, maar andere niet. Zo zijn er nu veel verschillende noties van randomness, zoals Martin-Löf randomness, computable randomness en Schnorr randomness. Dit zijn allemaal redelijke definities van randomness, maar de ene is sterker dan de andere. De studie van de relatieve sterkte en van de eigenschappen van deze noties staat centraal in algorithmic randomness, en heeft over de laatste jaren steeds meer aandacht gekregen.
Terug naar mijn wiskundepagina.