Den engelske matematiker Alan Turing, der i morgen ville være fyldt 100 år, udviklede i 1936 det teoretiske grundlag for den moderne computer.

I Alan Turings samtid blev ordet 'computer' stadig forstået som værende et menneske, der arbejdede med at beregne. Det var derfor en meget kontroversiel idé at betragte mentale processer som noget, der kunne splittes op i simple mekanisérbare operationer.

En såkaldt Turingmaskine er en abstrakt repræsentation af en regnemaskine. Selvom Turing ikke rent fysisk byggede den første 'moderne' computer, kan man med god ret sige, at Alan Turing på et teoretisk plan opfandt den første generelle og programmerbare digitale computer.

Den består af et læse- og skrivehoved, som kan aflæse tal på en tynd og meget, meget lang papirstrimmel, der kan skubbes frem og tilbage. Strimlen er inddelt i felter, hvorpå der står enten 0 eller 1.

Beregningen begynder, når maskinen aflæser det første felt, hvorefter skrivehovedet visker tallet ud og erstatter det med enten et 0 eller 1, hvorpå strimlen bevæges et felt frem eller et felt tilbage.

Turingmaskinens 'tilstand' er bestemt af et sæt regneregler, som er defineret fra starten. Dens aktuelle tilstand ændrer sig altså løbende i forhold til de ettaller og nuller, den møder på sin vej.

Maskinen kan for eksempel være i tilstand 7, hvor den har en regel om at skrive 0, når den møder 1, for derefter at bevæge strimlen et hak frem og gå over i tilstand 5.

Når den så læser et 0 i tilstand 5, kan reglen være, at den skal skrive 1, bevæge strimlen et hak tilbage og skifte til tilstand 12 osv.

Turingmaskinen er altså en mekanisk bureaukrat, som ikke behøver frokostpauser eller toiletbesøg. Den gør præcis de ting, den får besked på ved at slå op i en prædefineret og endelig tabel, som den kan huske, og derefter rykke rundt på ettaller og nuller.

Maskinen er software

I virkeligheden er en Turingmaskine en abstraktion af et computerprogram, snarere end en maskine - dvs. den er egentlig et stykke software, ikke hardware.

Man kan vise, at man kan lave Turingmaskiner, der på trods af deres ekstreme simpelhed kan beregne en hvilken som helst funktion, som en normal digital computer kan beregne. Den skal blot have nok tid og papir.

Turingmaskinen er derfor en konkret definition af, hvad en effektiv algoritme er. At en algoritme er effektiv, forstås her, som at den skal have et endeligt antal veldefinerede trin, der kan udføres mekanisk, og at den med det samme input altid skal producere det samme output.

På et idéhistorisk plan var Turingmaskinen meget vigtig, fordi den var en konkret realisering af Hilberts idé om at transformere hele matematikken til en formel mekanisk proces, hvor man ikke behøver andet end slavisk at følge et endeligt antal opskrifter for at bevise et hvilket som helst teorem.

Dette var formuleringen af Hilberts 'Entscheidungsproblem'. Turings svar var, at der ikke findes nogen 'Entscheidung', dvs. at der ikke findes nogen effektiv metode eller mekanisk procedure, ikke nogen computer eller noget computerprogram, som på forhånd kan afgøre, om et vilkårligt andet computerprogram stopper, dvs. får regnet sig færdig til et resultat eller ej.

Dette kaldes Turings 'stop-problem'.

Gödels ufuldstændighedsteorem fra 1931, der siger, at et formelt aksiomatisk system enten er inkonsistent eller ufuldstændigt, er så blot en naturlig følge af stop-problemet, for hvis man kan vise, at det er umuligt at afgøre, om et computerprogram stopper, så kan der heller ikke findes et fuldstændigt og konsistent sæt af aksiomer, med hvilke man kan slutte sig til, om en matematisk sætning kan bevises eller ej, idet aksiomerne jo ville kunne oversættes til en effektiv algoritme.

Grænser for formel tænkning

Gödels og Turings arbejder rejste væsentlige spørgsmål for grænserne for formel tænkning.

Selv det at antage, at noget var 'falskt' eller 'sandt' i matematisk forstand, var blevet problematisk, fordi begge kategorier var blevet beviseligt ubeviselige.

En anden væsentlig pointe i Turings arbejde var, at hans matematiske argument afhang af fysikkens natur - i dette tilfælde af beregnelighedens grænser via en effektiv computeralgoritme.

Det åbnede op for en meget tættere forbindelse mellem fysik og matematik end tidligere antaget. For hvis de logiske grænser for beregnelighed også gælder for alle regnemaskiner, vil en lang række problemer heller aldrig kunne løses i praksis.

Turings stop-problem og bestemte aritmetiske beslutningsproblemer vil aldrig kunne finde en løsning, selv med den størst tænkelige computer.

En lang række beregninger, som f.eks. sorteringen af elementer i en liste, vil kun kunne løses inden for et tidsrum, der er afhængig af problemets størrelse.

Det vil sige, at hvis problemet er for stort, vil det aldrig kunne løses i endelig tid.

Artiklen er et lettere redigeret uddrag af kapitlet 'Turing og den universelle maskine' fra bogen 'Ergo - naturvidenskabens filosofiske historie' af Robin Engelhardt og Hans Siggaard Jensen, L&R, 2007, s. 270-274.