menu close Teknologiens Mediehus
person Konto arrow_drop_down
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.
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.
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.
Artiklen indeholder en del vrøvl - sikkert som følge af forsimplinger.
For det første, kan sorteringsgitternet altid løses i endelig tid. Sorteringsgitternet kan foretages i tid O(n log n) eller O(n) afhængig af maskinmodel. Uanset hvor stort problemet er, vil det kunne løses hurtigt og altid terminers. Hele pointed med halting problematic er, det Ikke kan løses effektivt. Halting problemet er et af de lette svære problemer, og er semi-afgørligt. Dvs., man kan lave en algoritme, som kan svare ja hvis svaret er ja, men ikke nødvendigvis giver et svar hvis svaret er nej (det er endda simpelt: kør programmet, når det terminers, svar ja). Finten er, der ikke er bogen garanti for hvornår man får et svar, og man ved ikke om svaret er nej eller det bare tager lang tid at finde svaret.
Beviset for uafgørlighed af halling problemet er sågar simpelt. Antag vi har et program P, der afgør halling problemet for alle programmer. Lav nu et program, der tager et input, kører P på det og hvis P siger ja, lav en uendelig løkke. Ellers terminer. Kør nu det nye program på sig selv. P kan ikke svare rigtigt. Hvis P siger programmet terminerer, vil det loope og hvis P siger, programmet looper, vil det terminere. Ergo kan P ikke afgøre terminering for alle programmer.
men Ingeniør Konrad Zuse der har opfundet og lavet computeren i 1938. I 1935 tænkte han på, at det var "binary arithmetic", der er en fordel, i stedet for almindelige tal (der var også noget andet arbejde, der skulle passes).
Det var en PRAKTISK mand! Altså et år før Alan Turing havde tænke på det. Han fik startet et computer firma i 1943 i Tyskland, og havde er computer til at stå på Swiss Federal Technical Institute (ETH) fra 1946 til i hvertfald 1950 - 1952.
"His Z4 influencet continental European computing in the early 1950s".
Det var altså før, at Turing havde tænk på det, Tyskland tabte krigen, at han er "gået i glemmebogen" over det meste af verden (men tyskerne kan huske ham). Han er blevet 100 år i 2010!
Det kan ses på www.wikipadia.org/wiki/Konred_Zuse (mon ikke der har været en artikel i Ingeniøren for nogle år siden) og en hel masse andre steder.
Og jeg lærte om ham på et kursus i Aarhus.
mvh
Jens
"Selv det at antage, at noget var 'falskt' eller 'sandt' i matematisk forstand, var blevet problematisk, fordi begge kategorier var blevet beviseligt ubeviselige."
Den bid forstår jeg ikke helt? Gödels ufuldstændighedssætninger handler vel først og fremmest om beviselighed og ikke sandhed. Til gengæld siger den 1. ufuldstændighedssætning at der, givet et konsistent aksiomatisk system A (af f.eks. de naturlige tal), altid vil være sande sætninger, som vi ikke kan bevise.
Til gengæld er der intet til hinder for at vi kan tage en af disse sande, men ubeviselige i A, sætninger og finde et aksiomatisk system B der kan bevise den i stedet.
"... 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."
Det er vel lige netop det som Gödels sætninger sætter en stopper for? Turingmaskinen er vel især interessant, fordi det er en definition af beregnelighed, som på oplagt vis laver et bindeled mellem fysiske maskiner og den teoretiske forståelse af beregnelighed. Den var jo ækvivalent med beregnelighed som Gödel og Church allerede havde formuleret (omend mere 'matematisk').