De vader van de computer – zo wordt hij wel genoemd: Alan Turing. In 2012 is het honderd jaar geleden dat hij werd geboren. Dat wordt internationaal gevierd met een Turingjaar. En hoewel hij minder algemeen bekend is dan Charles Darwin of Albert Einstein, staat hij voor de informatica op dezelfde hoogte.

Frits Vaandrager, hoogleraar Informatica voor technische toepassingen aan de Radboud Universiteit Nijmegen, gaf recent een lezing over de grote Britse geleerde en oorlogsheld die zelfmoord pleegde, zeven jaar na het einde van de Tweede Wereldoorlog waarin zijn talent en persoonlijkheid cruciaal waren om Duitse berichten te decoderen.

‘De ideeën van Turing zijn in mijn werk dagelijks aan de orde. Eigenlijk heeft Turing aangetoond dat wat ik wil – de correctheid bewijzen van complexe software – in zijn algemeenheid gedoemd is te falen. Ik lig daar ’s nachts niet wakker van, omdat we tegenwoordig van heel veel software toch de correctheid kunnen aantonen.  Maar ik denk wel dat heel veel onderzoeksvoorstellen naar programmaverificatie zijn afgewezen vanwege de zogeheten Turinggrens, de grens van wat berekenbaar is.’

Turing  liet zien dat alles wat er te berekenen valt met een Turingmachine gedaan kan worden. Dat is een lint met gegevens die stap voor stap afgelezen worden en vertaald in rekeninstructies, waarna het antwoord op het lint geschreven wordt. Het idee dat één machine verschillende dingen kan doen, heeft Turing met haarscherpe precisie duidelijk gemaakt. ‘We zijn er met onze pc’s en smartphones helemaal aan gewend geraakt – maar het was revolutionair,’ zegt Vaandrager.

Turing droeg zelf ook een uitzondering aan op die berekenbaarheid: het is onmogelijk om met de ene Turingmachine te bewijzen dat de andere Turingmachine altijd correct werkt. Onvermijdelijk treedt er ergens een loop of tegenstrijdigheid op. Wanneer dat zo is, hangt af van de zogeheten Turinggrens, en die is bij complexe programma’s eerder bereikt.

‘Ik zit altijd te kijken hoeveel ruimte ik heb voor die grens. Want hoewel we dus niet kunnen bewijzen dat een computerprogramma altijd werkt, kunnen we in de praktijk vaak wel bewijzen dat het in bijna alle gevallen werkt, of in bepaalde omstandigheden.’
Het Institute for Computing and Information Sciences van de Radboud Universiteit zal in 2012 op verschillende manieren aandacht besteden aan Turing – hij is immers voor alle aspecten van de informatica van belang, vindt Vaandrager. Een programma wordt later bekend gemaakt.

Foto Frits Vaandrager: Jarno Verhoef/NWO