Alan Turing


(English version here)

Alan M. Turing (1912-1954)

Alan Mathison Turing zag het levenslicht op 23 juni 1912 in Paddington bij Londen.

Doordat zijn vader tot zijn pensioen in 1926 in India, toen nog Brits, werkte, groeide hij en z'n iets oudere broer voornamelijk in Engelse tehuizen op, waar expressie, originaliteit en creativiteit, niet echt aangemoedigd werden (wetenschappen was dus zeker uit den boze). Turing interesseerde zich echter wél voor de exacte vakken en amuseerde zich toen al met chemische experimentjes.

Van 1926 tot 1931 zat hij op een Engelse public school : Sherborne School, waar hij systematisch slechte punten haalde. Enkel voor wiskunde en andere wetenschapsvakken ging het beter, al waren de leerkrachten ook daar niet echt over te spreken (« His work is dirty »). Hij werd meer als een probleem voor de maatschappij beschouwd dan een toegevoegde waarde en ook in zijn verdere leven kreeg hij niet de waardering die hij verdiende.

In 1931 sleept hij een studiebeurs in de wacht voor King's College, Cambridge. Van dan komt Turings carrière in een stroomversnelling. In 1935 krijgt hij een ambt aan King's College. In 1936 krijgt hij de Smith's Price voor zijn werk in de kanstheorie. Hij lijkt af te stevenen op een succesvolle loopbaan als zuiver wiskundige. Z'n unieke geest drijft hem echter in een andere richting.

In 1933 had Turing kennis gemaakt met Russel en Whitehead's "Principia Mathematica" en daarmee met het gebied van de wiskundige logica. Bertrand Russel was van mening dat alles wat wiskundig waar is men logisch kan afleiden met behulp van een welomlijnde verzameling afleidingsregels. Maar er waren sinds dan veel vragen gerezen over hoe waarheid door om 't even welk formalisme gevat kon worden. In het bijzonder had Gödel in 1931 Russel's standpunt ontkracht door te tonen dat de wiskunde niet compleet is : er zijn ware stellingen over getallen die niet kunnen bewezen worden door de formele toepassing van deductieregels.

In 1935 hoorde Turing tijdens een lezing van de Cambridge topoloog M.H.A. Newman dat een gelijkaardig probleem, gesteld door Hilbert, nog steeds onopgelost was. Namelijk de vraag over de beslisbaarheid (Decidability), het zogenaamde Entscheidungsproblem : bestaat er, tenminste in theorie, voor elk wiskundig probleem een algoritme om te beslissen of dat probleem een oplossing heeft? Moest dit waar zijn, dan zouden alle wiskundige problemen herleid kunnen worden tot mechanisch tellen. Je zou dan om 't even wat mogen poneren, een gepast algoritme erop loslaten en kijken of het resultaat waar of vals is.

Om op deze vraag te antwoorden heb je eerst en vooral een precieze definitie nodig van wat een algoritme juist is. Voor zo'n definitie zorgde Turing.

De Turing machine

Een Turing machine is een abstractie, een schepping van logica en wiskunde. Dit is verschrikkelijk vaag als uitleg, maar het basisconcept kunnnen we vergelijken met een willekeurig spel bv. monopolie. In monopolie concentreren we ons op een wereld waarvan de logica geheel beheerst wordt door de regels van het spel en bekommeren we ons niet om gebeurtenissen buiten het spel. In monopolie kan je kopen, verkopen, je pion bewegen etc., waar de regels niet over spreken is wat er gebeurt als je pion honger krijgt of in slaap valt. Dat doet er immers allemaal niet toe, een goed spel is in zichzelf besloten. Een Turing machine is ook zo'n logisch besloten wereld. De enige bewoner van deze wereld is een logische machine.

De machine bestaat uit een eindige verzameling ingebouwde regels en deze blijven vast gedurende heel het rekenproces. Verder hebben we een band van onbeperkte lengte waar informatie opgeslagen kan worden. Over het algemeen is die band in cellen verdeeld, die elk maar één symbool mogen bevatten. Ook is er een kop (read-write-head) om aan te geven welke cel op een gegeven moment wordt geïnspecteerd. De band bevat de informatie die de machine moet verwerken, hij kan tussentijdse resultaten bijhouden en bevat uiteindelijk ook het resultaat van de algoritme.

In het voorbeeld bevat een cel op de band enkel binaire informatie, ttz. 0, 1 of niets. De machine mag over ingevoerde informatie schrijven en het aantal cellen waarin iets staat is eindig.

De verzameling regels bepaalt dan de activiteit van de kop langs de band. Een Turing machine kan zoveel regels hebben als diegene die haar maakt wil, maar wel eindig. De machine is aan volgorde gebonden : ze activeert een regel, voert de acties bij die regel uit en activeert dan een andere regel. Voor en na de toepassing van zo'n actie bevindt de machine zich in één van een eindig aantal (toe)standen. Deze standen zijn net als de regels gedefinieerd door diegene die de machine heeft geconstrueerd.

De machine weet altijd twee dingen : haar huidige toestand en de huidige cel waar de kop op de band naar verwijst. Die twee zaken zijn de enige die de machine nodig heeft, dankzij haar huidige toestand en symbool in de cel weet men welke regel men moet toepassen. Wat zegt zo'n regel altijd :

  1. welk symbool je moet schrijven op de cel die door de kop wordt aangewezen. (hetzelfde symbool erover schrijven, komt neer op het gewoon laten staan van het symbool).
  2. De kop 1 (soms ook geen) plaats naar links of rechts schuiven .
  3. De huidige toestand veranderen in een nieuwe toestand.

Die drie dingen zijn de enige middelen waarmee een Turing Machine gegevens kan behandelen. Het proces gaat op deze wijze voort tot de machine een regel activeert die haar opdraagt te stoppen (het kan ook dat de machine stopt als er geen regel meer toepasbaar is, dit hangt van de ontwerper af).

Een Turing machine is een spel waar geen plaats is voor initiatief van de speler. Het enige element dat mag variëren is de invoerband. Zodra een bepaalde invoer is uitgekozen roept de machine haar regels op : elke invoer heeft één of geen mogelijke uitvoer. Merk op dat een Turing machine zichzelf niet kan wijzigen, enkel de data op de invoerband kan veranderd worden.

Voorbeeld

Stel dat de enige symbolen 0,1 en blanco zijn en dat we 5 toestanden hebben. Toestand 1 is de begintoestand van de machine en als we in toestand 5 geraken dan stopt de machine.

De regels kunnen er bijvoorbeeld als volgt uitzien :

Huidige toestand

Huidig symbool

Schrijf

Beweeg kop

Nieuwe toestand

1

0

0

Rechts

2

2

0

0

Rechts

3

2

1

1

Rechts

2

3

0

Blanco

Links

5

3

1

0

Links

4

4

0

1

Rechts

2

De eerste lijn wil dan zoveel zeggen als : wanneer je huidige toestand de eerste toestand is en de kop leest het symbool nul, schrijf dan een 0 over die 0 (laat het staan), beweeg de kop één naar rechts en de toestand waar je dan in bent is toestand 2.

De Turing machine met deze regels, toestanden en gepaste invoer voert een optelling uit van natuurlijke getallen. We noteren de getallen op de invoerband unair : stel je wil een paar getallen x en k voorstellen die je wil optellen, dan schrijf je een nul, vervolgens x ééntjes, een nul, k ééntjes en je eindigt weer met nul. (2,3) is zo 01101110.

Deze Turing machine telt getallen op, dus als je 01101110 als invoer geeft, moet je 0111110 terugkrijgen.

Hieronder zie je hoe dat gebeurt.

getal (unair)

Huidige Toestand

Actie

01101110

1

De kop staat op symbool nul, en de huidige toestand is 1, dus door de eerste regel schrijven we een nul (de nul laten staan), schuiven we de kop één naar rechts en gaan we naar toestand 2.

01101110

2

In toestand 2, lees je voorbij de 1, vermits er daar nog een 1 staat doe je terug hetzelfde, niets namelijk, en je verplaatst de kop naar rechts. Merk op dat je in toestand 2 blijft zolang je ééntjes blijft lezen.

01101110

2

Als je in toestand 2 bent (en dus het eerste getal aan het inlezen bent) en je komt een nul tegen, wil dit zeggen dat je het eerste getal gelezen hebt en je mag dus naar toestand drie.

01101110

3

De intuïtie is nu dat je alle ééntjes die je tegenkomt, bij de ééntjes die je al had moet plakken, je zet een 0 waar je staat, je gaat nu naar links en zet de toestand op 4. Er staat dan 01100110.

01110110

4

Vermits je in toestand 4 bent, en je leest een nul, schrijf je een 1 (dit is de één die je daarstraks weggegooid hebt), en je doet terug alsof je in het eerste getal aan het werken bent, dwz je gaat terug naar toestand 2.

01110110

2

Je komt dan terug een nul tegen (altijd, want je hebt die daar nl. gezet bij het terugggaan) en je gaat naar toestand 3.

01110110

3

Herhaling

01110010

4

Herhaling

01111010

2

Herhaling

01111010

3

Herhaling

01111010

4

Herhaling

01111100

3

Nu ben je in toestand 3, maar er is geen tweede getal meer, want je hebt een nul, en twee opeenvolgende nullen kan niet in unaire notatie, dus schrijf een blanco over die laatste nul en ga naar toestand 5.

0111110

5

Dit is de eindtoestand

Er bestaan een oneindig aantal andere, interessantere Turing machines, maar de werkingsprincipes zijn steeds dezelfde, voor welk doel de machine ook gemaakt is. De band zou de cijfers van een getal kunnen bevatten en de machine kan dan regels hebben om de vierkantswortel van dit getal te trekken.

De werkelijke uitdaging ligt in het ontwerpen van de Turing machine zelf : het opstellen van regels en het bepalen van standen die de machine op de gewenste manier zullen laten werken.

Welke ook nog belangrijk is, is de Universal Turing machine. Elke Turing machine is een hoop toestanden , regels, invoersymbolen,… . Het is dan min of meer duidelijk dat er één universele Turing machine kan gebouwd worden die genoeg regels, toestanden en dergelijke heeft om elke Turing Machine te simuleren.

Dit begint verdacht veel op een computer te lijken. Op één computer (universal Turing machine) kan je verschillende software (Turing machines) draaien. Met een computer informatie verwerken is niets anders dan afzonderlijke symbolen één voor één vervangen volgens een eindig stel regels. Iedere taak die een computer uitvoert (van het uitrekenen van belasting tot schaak spelen) kan door deze vervangingsprocedure verklaard worden en iedere taak die door deze vervangingsprocedure niet kan uitgevoerd worden kan niet voor een computer geprogrammeerd worden.

We komen nu terug op de vraag die de oorsprong is van die Turing machines : bestaat er voor een stelling, een algoritme dat zegt of die stelling waar of vals is? Een algoritme is niets anders dan een aantal wiskundige operaties na elkaar. Turing bewijst dat je die wiskundige operaties in een eindig aantal fundamentele bouwstenen kan ontbinden. Hij toont dat je met de betrekkelijk eenvoudige Turing machines elk willekeurig algoritme kan simuleren (ergens hoopte hij zelfs dat de Turing machine alles kan wat het menselijke brein kan - bewuszijn inbegrepen).

Nakijken of een algoritme met als invoer een stelling waar of vals is, komt dan neer op nakijken of een Turing machine met een bepaalde invoer een oplossing geeft of niet, dus of de Turing machine in een oneindige lus komt of niet. Vraag is : kunnen we op voorhand zeggen of een Turing machine bij een invoer gaat stoppen of niet? Nee. We kunnen pas zeggen dat de Turing machine gaat stoppen met berekenen, als ze daadwerkelijk gestopt is (het "halting problem"). Analoog kunnen we pas zeggen dat een stelling waar is, als er een bewijs voor is.

Nog anders gezegd : elke berekening die mechanisch (algoritmisch) kan uitgevoerd worden, kan door een Turing machine uitgevoerd worden. Omgekeerd als het niet door een Turing machine kan uitgevoerd worden, dan is het niet berekenbaar.

We zullen nu een schets zien van het bewijs dat Turing had. Zijn stelling is : er bestaat geen mechanische procedure om te zien of een Turing machine stopt bij gegeven invoer.

Het is duidelijk dat er oneindig veel, maar een aftelbaar aantal Turing machines zijn. We kunnen alle Turing machines daarom in een lijst zetten : T1, T2,...

We stellen dan het resultaat van de n-de machine Tn met invoer i voor als Tn(i).

Door contradictie :

Veronderstel dat er wel een regel of procedure bestaat om te beslissen of Tn(i) stopt voor alle waarden n en i.

Zet dan alle Turing machines met hun invoer en uitvoer in een tabel.

Daar waar vraagtekens staan stopt de Turing machine niet, dit weten we door de hypothese, bv. bij T1(4). Via een soort diagonalisatieprocedure (cfr Cantor) kunnen we dan een machine D maken die altijd stopt voor om ’t even welke invoer. D(i) is :

0 als Ti(i) niet stopt.
Ti(i)+1 als Ti(i) stopt.

Maar D moet dan één van de Ti zijn (vermits dit ze allemaal zijn). Er is dus een d waarvoor D = Td. Maar we hebben D juist zo gedefinieerd dat het verschillend was van alle Ti . Contradictie.

En dus bestaat er geen procedure om te bepalen of de Turing machine stopt bij gegeven invoer.

Zoals we zien ligt de moeilijkheid niet bij het bewijs van het feit dat we niet kunnen weten of een Turing machine stopt maar wel hoe de Turing machine bouwen die een bepaald algoritme simuleert.

In april 1936 toonde hij zijn resultaten aan Newman; maar tegelijkertijd raakte de parallele conclusie van de Amerikaanse logicus Alonzo Church bekend, en die beroofde Turing min of meer van de volle beloning voor z'n originaliteit. De paper, "On Computable Numbers with an application to the Entscheidungsproblem" moest naar Church zijn werk verwijzen en het uitgeven ervan werd uitgesteld tot augustus 1936. Church had dus dezelfde conclusie voor Hilberts probleem, maar men zag toen wel al in dat Turings benadering origineel en verschillend was.

Church steunde op veronderstellingen inherent aan de wiskunde, terwijl Turing zich baseerde op in de werkelijkheid uitvoerbare operaties door dingen of mensen. Inderdaad als je iets moet bewijzen over wiskunde zou het wel eens veiliger kunnen zijn dit te bewijzen zonder gebruik te maken van de wiskunde, kwestie van circulaire redeneringen en contradicties allerhande te vermijden.

Alonzo Church tenslotte postuleerde dat er geen krachtiger systeem om berekeningen mee uit te voeren kan zijn dan een Turing machine. Het is alleszins moeilijk om zo'n nog krachtiger systeem in te denken, vermits dat systeem dan problemen zou kunnen aanpakken die men niet eens op een gestructureerde manier kan oplossen. Sommigen stellen het menselijke verstand voor als zo'n systeem.

Als we Church volgen en zeggen dat de Turing machine het krachtigste is dat er is, dan zou ook het brein niet krachtiger zijn en bijgevolg gesimuleerd kunnen worden door een Turing machine (hier haken de meeste mensen echter af).

Wat er ook van zij, het blijft een feit dat een zo eenvoudig ding als de Turing machine in staat is tot dingen waar om 't even welke hedendaagse computer toe in staat is, al moeten we er wel bij zeggen dat de uitvoering van een taak een "ietsje" langer zal duren. Terecht werd de Turing machine dan ook één van de fundamenten van de moderne theorieën over computers en berekenbaarheid.
In 1938 bood men Turing een tijdelijke post aan in Princeton, maar in plaats daarvan keerde hij terug naar Cambridge. In 1938 en '39 leefde hij van z'n ambt aan King's College als logicus en getaltheoreticus.

Halftijds werkte hij voor het Britse cryptoanalytische departement (verantwoordelijk voor het ontcijferen van geheime boodschappen), de zogenaamde "Government Code and Cypher school". Z'n benoeming hier viel samen met de intrede van de wetenschappelijke aanpak in het departement welke daarvoor een "op-kunst-gebaseerde-afdeling" was. Die revolutie was grotendeels veroorzaakt door het falen van niet-wetenschappelijke methodes om tot de mechanisch gegenereerde Enigma codes, gebruikt door Nazi-Duitsland, door te dringen.

Bijna alle Duitse communicaties werden gecodeerd door de Enigma machine. Deze was gebaseerd op bewegende rotors die altijd-veranderende alfabetische substituties produceerden. Men beschouwde de code door de Enigma machine als niet te breken, zelfs niet door iemand in het bezit van de machine zelf.

In het breken van de code werd dan ook nauwelijks vooruitgang gemaakt tot er in juli 1939 vitale informatie van Poolse wiskundigen kwam, die al veel langer met het probleem in de weer waren.

Bij de Britse oorlogsverklaring in september '39 trad Turing voltijds in dienst in het cryptoanalytisch hoofdkwartier in Bletchley Park. De Poolse methode had zijn beperkingen in de zin dat ze afhankelijk was van de Enigmaboodschap. Turing maakte een generalisatie van hun systeem dat in staat was elke Enigmaboodschap te kraken, als er maar een klein stukje tekst correct kon geraden worden.

Een andere Cambridgewiskundige W.G. Welchman leverde nog een belangrijke bijdrage, maar de kritieke factor was Turings briljante mechanisatie van subtiele logische deducties.

Rechts : de Enigma machine

Toen op 1 februari 1942 de Enigma machine die de communicatie tussen onderzeeërs codeerde een extra rotor kreeg was het weer om zeep en catastrofe dreigde.

Een logische zwakheid ergens in het systeem loste ook dit op en dit tot het einde van de oorlog.

Dit was allemaal belangrijk in de zin dat de ingenieurs tot het bedenken van steeds snellere machines gedwongen werden. Het eerste gebruik van een elektronische ontcijfermachine bleef dan ook niet uit. Net voor D-day was er zo al één in gebruik : de "Collosus".

In 1944 was Alan Turing ongeveer de enige met de volgende 3 ideeën:

  1. z'n eigen concept van de universele Turing machine.
  2. Het potentieel aan snelheid en betrouwbaarheid van de opkomende elektronische technologie.
  3. De inefficiëntie van het ontwikkelen van verschillende machines voor verschillende logische processen.

Gecombineerd leverden deze drie ideeën het principe, de praktische middelen en de motivatie voor de moderne computer : één enkele machine in staat elke geprogrammeerde taak uit te voeren.

Hijzelf stond te springen om dit alles in realiteit om te zetten en werd nog enthousiaster door een vierde idee : de universele machine zou de mogelijkheden van het menselijke brein moeten kunnen verwerven en tentoonstellen.

Na de tweede wereldoorlog werkte hij voor het National Physical Laboratory (NPL) en zette hij zijn onderzoek naar computers voort. Hij werkte aan de ontwikkeling van de Automatic Computing Engine (ACE) : één van de eerste pogingen een echte digitale computer te bouwen. Hij verliet het NPL echter, nog voor de afwerking van de ACE en verhuisde in 1948 naar de universiteit van Manchester, waar men werkte aan de Manchester Automatic Digital Machine (MADAM).

Turing had de wereld daar al in de software-ontwikkeling kunnen leiden. Onder zijn gedeeltelijk onderzochte ideeën waren het gebruik van wiskundige logica om programma’s na te kijken, het implementeren van Church zijn logica calculus op de machine, en andere zaken die gecombineerd met z'n massieve kennis van combinatorische en statistische methoden, de agenda van de computerwetenschappen voor jaren hadden kunnen vastleggen. Hier slaagde hij echter niet in.

In de plaats daarvan volgde een verwarde periode, waarin Turing schipperde tussen oude en nieuwe onderwerpen. Toch kwam uit deze tijd de meest heldere en ver- strekkende uitdrukking van Turings filosofie over machine en geest : de paper Computing Machinery and Intelligence dat verscheen in het filosofische bladMind in 1950. In dit artikel beschrijft hij de Turing test (hij noemde dit "imitation game"), een test om te zien of een computer/machine intelligent is of niet. Deze test is tot de dag van vandaag een veelbesproken onderwerp in de artificiële intelligentie. De 1987 editie van de Oxford Companion to the Mind beschrijft de test als "the best we have for confirming the presence of intelligence in a machine".

De Turing test :

Een persoon communiceert met de computer via een terminal. Wanneer de persoon niet kan beslissen of hij met een computer praat of een andere persoon, kan men zeggen dat de computer alle belangrijke eigenschappen van intelligentie heeft. Turing was ervan overtuigd dat men zo’n machine kan bouwen.

In de jaren voor z’n dood werkte hij aan iets totaal anders, namelijk de oorsprong van biologische vormen – Morphogenesis. Zoals alles waar hij zich voor inzette, leverde hij ook hier verdienstelijke bijdragen.

Maar in 1952 werd Turing gearresteerd nadat de politie te weten was gekomen dat hij een sexuele relatie had met een man, een misdrijf in het Engeland van die tijd. Hij had de keuze tussen gevangenisstraf of gedurende een jaar een hormonale behandeling te ondergaan. Turing "koos" voor het laatste.

De overheid was er zich van bewust dat Turing tijdens de oorlog op de hoogte was geweest van zaken die het daglicht schuwen. En nu hij bovendien als "niet veilig" werd beschouwd, hield men hem goed in 't oog. De contacten die Turing met het buitenland had bekeek men dan ook argwanend, met een huiszoeking in maart 1953 als gevolg.

Turing geraakte hier vrij depressief van en kwam op 7 juni 1954 aan z'n einde. Zeker is dat hij een appel vergiftigd met cyanide at. Of het zelfmoord of een ongeluk met een chemisch experiment was, daar is men het niet over eens.

Bronnen:

  1. Turing's man door J. David Bolter,The North Carolina University press,1984.

  2. Gödel, Escher,Bach : an Eternal Golden Braid door Douglas R. Hofstadter,Basic Books,1979.
(back to top)
Last modified by stijnh1@yahoo.com on .