Hypercomputere og beregning af det uberegnelige
Nutidens computere er alle modelleret efter principper, som Alan Turing beskrev i 1936.
Med bl.a. IBM’s Watson-maskine, der har vundet Jeopardy i USA, er disse såkaldte universelle Turing-maskiner, som først så dagens lys efter Anden Verdenskrigs afslutning, nu videreudviklet og perfektioneret til næsten fuldkommenhed.
Watson, og alle andre supercomputere og fremtidige kvantecomputere for den sags skyld er dog stadig Turing-maskiner, og der er derfor visse ting, som disse aldrig nogensinde kommer til at beregne.
Det interessante spørgsmål er, om man kan designe og fremstille maskiner, der er så fundamentalt anderledes, at de så at sige kan beregne det uberegnelige.
Sådanne hypotetiske maskiner er givet navne som hypercomputere og superturing-maskiner, og de er varianter over det, som Alan Turing selv kaldte orakel-maskiner.
Gennem mange år har der været en til tider intens og ophedet diskussion blandt eksperter om, hvorvidt en hypercomputer er andet end et abstrakt logisk begreb, og hvad der i givet fald hindrer en fysisk realisering.
En relateret problemstilling er, om hjernen er en sådan hypercomputer, og om denne kan efterlignes i en eller anden form for maskine.
Turing-maskiner har flere begrænsninger. En af dem er, at en sådan ikke generelt kan afgøre, om den stopper og leverer et ønsket resultat, eller om den kommer ind i en uendelig løkke.
En hypercomputer vil kunne løse dette såkaldte halting problem. Den vil vide, om den er endt i en uendelig løkke, eller om den på et tidspunkt kommer ud af en længerevarende tilsyneladende inaktivitet og er klar til andre gøremål. Det er en viden, som enhver bruger af computere vil være lykkelig for at få.
Uenigheden blandt eksperterne om hypercomputere går så vidt, at de langtfra er enige i om, hvordan de skal fortolke de tanker, Alan Turing og andre af hans samtidige gjorde sig om, hvad maskiner kan beregne.
Filosoffen Jack Copeland fra University of Canterbury i New Zealand beskæftigede sig i sidste uge med disse spørgsmål ved forelæsninger på Københavns Universitet, hvor han de seneste måneder har været gæsteprofessor.
Jack Copeland opfandt ordet hypercomputer i en artikel i 1999 i Scientific American, hvor han skrev en artikel om det, han kaldte Alan Turings glemte ideer inden for computervidenskab.
Han er en af verdens førende eksperter i den filmaktuelle Alan Turings værker og tankegang, og vi skal helt tilbage til Alan Turings banebrydende artikel On computable numbers fra 1936 for at finde udgangspunktet for den nuværende diskussion.
David mod Goliat
I denne artikel tog den på daværende tidspunkt ukendte 24-årige britiske ph.d.-studerende et opgør med datidens matematiker over dem alle, tyske David Hilbert, som var berømt for i 1900 at have sat hele tonen for den matematiske udvikling i det tyvende århundrede med en liste over store uløste problemer.
I 1928 opstillede Hilbert en ny udfordring i form af det såkaldte Entscheidungsproblem (beslutningsproblem), der sigtede mod at mekanisere eller automatisere den måde, hvorpå man kan lave matematiske beviser.
Ind fra sidelinjen kom Alan Turing og viste, at den tyske mester tog fejl, når han mente, at det ville være muligt at lave en sådan algoritme, der helt generelt kunne afgøre, om noget var rigtigt eller forkert.
Turing gav et matematisk bevis for, at der er visse ting – eller visse tal – en maskine ikke kan beregne.
Tallet pi er som bekendt et irrationalt tal med uendeligt mange cifre efter decimalkommaet. Til trods herfor er pi et beregneligt tal, idet vi kan stille en computer den opgave at finde ciffer n efter kommaet, og den vil kunne gøre det, uanset om n er 1.000, 1 million, 1 milliard eller et hvilket som helst andet tal.
Der findes dog irrationale tal, for hvilket dette ikke er muligt – og derfor kaldte Turing sin artikel ‘On computable numbers’.
Men hvad er egentlig en computer, kan man med rette spørge?
På Alan Turings tid var en computer et menneske, der udførte matematiske beregninger. Computere var ansat i forsikringsselskaber, ved forskningsinstitutioner (civile eller militære) og andre steder, hvor der skulle udføres mange beregninger.
Computere fik udleveret datamateriale og en forskrift for de beregninger, de skulle udføre. I mange tilfælde anede de ikke, hvad deres beregninger skulle bruges til. De regnede blot løs – præcis som vores maskinelle computere gør det i dag.
Alan Turing definerede i sin artikel en beregningsmaskine (computing machine) som en idealiseret udgave af en menneskelig computer, dvs. en universel maskine, der kan udføre alle tænkelige opgaver i henhold til et program lagret i computeren. Og det blev efter den opskrift, de første universelle computere blev lavet.
Men som Alan Turing havde vist, var der visse funktioner eller tal, som en sådan maskine – som senere fik navnet en Turing-maskine – ikke kunne beregne.
Den amerikanske matematiker Alonzo Church havde samtidig, på anden vis, bevist det samme. I dag er den fælles indsigt samlet i den såkaldte Church-Turing-tese. Problemet er, at den formuleres på forskellig vis, hvor Jack Copeland skelner mellem to hovedformuleringer.
Den første, som er den Copeland tillægger Turing, lyder i Copelands formulering sådan:
‘En universel Turing-maskine kan udføre enhver beregning, som kan udføres af en menneskelig beregner’.
Alan Turing var nemlig i sin artikel inde på, at man kunne forestille sig et såkaldt orakel, der kunne give svar på spørgsmål, en universel Turing-maskine ikke kunne beregne. Ved at inkludere oraklet ville man få en såkaldt o-maskine, der ville udføre beregninger på anden vis end en menneskelig computer.
Hvordan sådan en o-maskine skulle kunne laves, gjorde Alan Turing sig ingen tanker om i 1936.
Den anden hovedvariant af tesen lyder: ‘Alt, som kan beregnes med enhver form for maskine, kan beregnes med en universel Turing-maskine.’
I dette udsagn ligger implicit, at o-maskiner ikke findes. Denne kalder Jack Copeland for M-tesen, hvor M står for maksimum, forstået på den måde, at det er det maksimalt stærke udsagn.
Når Turing i det hele taget beskrev den logiske mulighed af o-maskiner, var det i følge Jack Copeland fordi, Turing mente, at der var forskel på matematikere og menneskelige computere.
En menneskelig matematiker kunne med hjælp af intuition eller anden form for indsigt udføre opgaver, som en mekanisk orienteret menneskelig computer ikke kunne.
Jack Copeland forklarer, at Turing anså, at hjernen til enhver tid fungerede som en Turing-maskine – men som forskellige maskiner på forskellige tidspunkter. Der var knyttet en form for tilfældighed til springene mellem forskellige ‘maskiner’ – og derfor ville hjernen i det lange løb være uberegnelig.
Et af de tal, som Turing viste var uberegneligt med en computer (menneske eller maskine) efter en mekanisk forskrift (program), anså han for i princippet at kunne beregnes af en matematiker ved, at denne skiftede mellem forskellige metoder.
Jack Copeland mener, det interessante spørgsmål derfor er, om man kan overføre dette til en ny form for beregningsmaskine.
Mange mener dog, at fysikkens love forbyder en realisering af hypercomputere. Kritikere mener eksempelvis, at det vil kræve, at en uendelig mængde information skal findes inden for et endeligt afgrænset område – hvad der er umuligt. Jack Copeland mener dog at have tilbagevist denne påstand.
Han står da heller ikke alene med at spekulere i og mere konkret undersøge muligheden for nye metoder til design af computere, som andre kloge hoveder anser for en håbløs mission.
Turingeksperten Andrew Hodges, hvis bog ligger til grund for den biografaktuelle film ‘The Imitation Game’ om Alan Turing, mener, at Jack Copeland helt har misforstået budskabet i Turings artikler, og han har kaldt Copelands artikel i Scientific American fra april 1999, hvor ordet hypercomputation blev lanceret, for en aprilsnar.
Da en anden førende Turingekspert, Martin Davis, der er professor emeritus ved New York University, i 2006 blev bedt om at skrive en introduktion til en særudgave af tidsskriftet Applied Mathematics and Computation om hypercomputere, leverede han et indlæg på fire sider med titlen ‘Why there is no such discipline as hypercomputation’.
Fakta: Analog superturing-maskine måske på vej
Hava Siegelmann, der i dag er professor ved University of Massachusetts i USA, lancerede i midten af 1990’erne tanker om en analog computer i form af et neuralt netværk, der kunne udføre beregninger, der ikke er mulige med digital Turing-maskine.
Hendes artikel i Science i 1995 blev mødt med kritik fra bl.a. matematikeren Peter Shor, der i dag er kendt for en algoritme, som kan udnyttes af kvantecomputere til et knække krypteringsnøgler. Han anerkendte dog, at spørgsmålet om, hvorvidt analoge computere ville kunne overgå digitale computere, var vigtigt at tage fat på.
Steven Younger og Emmett Redd fra Missouri State University arbejder i disse år på at realisere Siegelmanns tanker. De mener, at denne form for superturing-maskine ikke er udsat for de fundamentale begrænsninger, som andre forskere tillægger mere generelle hypercomputere.
...men det er dyrt at lave god journalistik. Derfor beder vi dig overveje at tegne abonnement på Version2.
Digitaliseringen buldrer derudaf, og it-folkene tegner fremtidens Danmark. Derfor er det vigtigere end nogensinde med et kvalificeret bud på, hvordan it bedst kan være med til at udvikle det danske samfund og erhvervsliv.
Og der har aldrig været mere akut brug for en kritisk vagthund, der råber op, når der tages forkerte it-beslutninger.
Den rolle har Version2 indtaget siden 2006 - og det bliver vi ved med.
