At forudsige det uforudsigelige

I den kommende uge skal jeg for hvem ved hvilken gang undervise et hold studerende i uafgørbarheden af acceptproblemet for Turing-maskiner. Hver gang jeg skal undervise i dette, spekulerer jeg en del over om de studerende vil forstå ikke bare beviset for dette vigtige resultat, men også hvorfor det er så vigtigt. Det er nemlig et matematisk resultat, der siger hvad algoritmer aldrig vil kunne.

Sætningen om uafgørbarheden af acceptproblemet siger, uformelt sagt, at det rigtige svar på beslutningsproblemet

Givet en algoritme M og et stykke data w, gælder det da at M vil acceptere (dvs. terminere som ønsket) hvis den køres med w som input?

kan ikke forudsiges af nogen algoritme, der tager M og w som parametre. Dette vigtige resultat, der skyldes Martin Davis (og faktisk er en omformulering af en sætning, der skyldes Alan Turing og er fra 1936) fortæller os, at algoritmer ikke kan bruges til at forudsige hvordan algoritmer vil opføre sig.

Jeg kommer her til at tænke på en kort tekst af den amerikanske forfatter og matematiker/datalog Rudy Rucker:

A little-known truth: Every aspect of the world is fundamentally unpredictable. Computer scientists have long since proved this.

How so? To predict an event is to know a shortcut for foreseeing the outcome in advance. A simple counting argument shows there aren’t enough shortcuts to go around. Therefore most processes aren’t predictable. A deeper argument plays on the fact that, if you could predict your actions, you could deliberately violate your predictions which means the predictions were wrong after all.

We often suppose that unpredictability is caused by random inputs from higher spirits or from low-down quantum foam. But chaos theory and computer science tell us that non-random systems produce surprises on their own. The unexpected tornado, the cartoon safe that lands on Uncle George, the winning pull on a slot machine odd things pop out of a computation. The world can simultaneously be deterministic and unpredictable.

Beviset for uafgørbarheden består egentlig i at udfolde ideen i Ruckers bemærkning om “A deeper argument…” – der er nemlig en selvreference begravet i bemærkningen. Om man kan forestille sig en lignende bevisstrategi for at argumentere for uforudsigelighed inden for fysik, ved jeg ikke. Den skulle måske gøre brug af at mennesket selv er et fysisk system snarere end at falde tilbage på kaosteorien. Populære appeller til kaosteori består ofte i at sige “…men det hele er jo så uoverskueligt”. Det implicerer imidlertid ikke, at naturfænomener principielt er uforudsigelige.

I den manglende evne til at forudsige har vi vel egentlig naturvidenskabens store metodologiske paradoks. Naturvidenskab handler i stort omfang netop om at opstille love, der gør det muligt at forudsige hændelser! Især i anvendelsernes domæner bliver forudsigelserne vigtige. Meteorologerne vil forudsige vejret. Medicinerne vil forudsige om en behandling virker. Bygningsingeniørerne vil forudsige, om en konstruktion kan bære. Og softwareudviklerne vil forudsige, om et stykke software kan udvise bestemte fejltyper.

Og det er jo faktisk lykkedes at opstille naturvidenskabelige modeller, der er i stand til at forudsige rigtig meget! Noget kan naturvidenskaben jo trods alt. Ellers gav vi jo op og tog hjem for at se fjernsyn (hvordan fjernsynet så skulle være blevet opfundet, ved jeg så ikke). Jeg fæster f.eks. stor lid til formlerne for skråt kast. Bygningsingeniører er voldsomt gode til at forudsige, om en konstruktion kan bære. Og dataloger bruger en masse tid og kræfter på at finde specialtilfælde af acceptproblemer, hvor det faktisk er muligt at finde ud af om M kan acceptere input w.

Så måske handler det i virkeligheden mere om at udforske forudsigelighedens grænser?