Hypercomputeren beregner det uberegnelige

Af Palle Vibe, Alt om Data

Denne artikel er oprindeligt bragt på Alt om Data. Computerworld overtog i november 2022 Alt om Data. Du kan læse mere om overtagelsen her.

Siden den navnkundige britiske matematiker Alan Turing udregnede grundlaget for den elektroniske computer under betegnelsen ”universel Turing-maskine” i 1936, er de digitale beregnere blevet udviklet og perfektioneret i en grad, så de bedste i dag kan vinde over enhver i skak og paratviden og måske ligefrem er på nippet til at gøre os rangen stridig som intelligente væsner.

Men der er grænser for deres formåen. Der er visse ting, som disse beregnende robotter aldrig nogensinde kommer til at beregne. Og spørgsmålet er, om det nogensinde vil kunne lade sig gøre at konstruere en computer, der er så fundamentalt anderledes, at den kan beregne det, som i dag er nærmest uberegneligt, for eksempel matematiske beviser?

Menneskelige computere

På Alan Turings tid var en ”computer” en menneskelig beregner. Disse dygtige talknusere i kød og blod var ansat i banker og forsikringsselskaber eller arbejdede for forskningsinstitutioner eller lignende. Ofte anede de ikke, hvad de rent faktisk beregnede, eller hvad resultaterne skulle bruges til. De fik bare udleveret råt talmateriale og en opskrift (program), og så regnede de løs – præcis som digitale computere gør det i dag.

Måske var det derfor, at Alan Turing definerede en elektronisk beregningsmaskine som det mekaniske svar på den menneskelige hjerne. En maskine, der kunne udføre alle tænkelige beregningsopgaver, når blot den fik fortalt hvordan i form af en opskrift eller et program.

Men Alan Turing mente også, at det ville være muligt at lave en såkaldt orakel-maskine, der kunne lave beregninger på andre måder end både en menneskelig computer og en universel Turing-maskine. Han publicerede sine tanker i en berømt artikel under overskriften ”On computable numbers”.

I artiklen går den på det tidspunkt ukendte 24-årige ph.d.-studerende ind og undsiger tidens store, berømte tyske matematiker David Hilbert, som i 1928 havde opstillet det såkaldte ”Entscheidungsproblem” (beslutningsproblem), der søgte at beskrive, hvordan det kunne være muligt at mekanisere eller automatisere beregning af matematiske beviser. Eller med andre ord udvikle en algoritme, der helt generelt og matematisk er i stand til at afgøre, om noget er rigtigt eller forkert. Turing demonstrerede med et dygtigt matematisk bevis, at der er visse funktioner og irrationelle tal, en almindelig computer aldrig vil kunne beregne.

På vej mod hypercomputeren

Filosoffen Jack Copeland fra University of Canterbury i New Zealand, der tidligere i år gæstede København for at holde foredrag om emnet, opfandt et nyt ord for Turings omstridte maskine i en artikel fra 1999 i tidsskriftet Scientific American. I artiklen gør han sig blandt andet forestillinger om, hvordan en computer, der kan beregne det uberegnelige, egentlig kan fungere, og han giver sådan en computer betegnelsen ”hypercomputer”.

Jack Copeland uddyber Alan Turings tanker om hypercomputing. For selv om Turing reelt betragtede menneskehjernen som en universel Turing-maskine, syntes den dog at optræde som forskellige maskiner på forskellige vilkårlige tidspunkter. Og da disse vilkårlige tidspunkter ikke var forudberegnelige, var den menneskelige hjerne i hvert fald i det lange løb også uberegnelig.

Turing mente eksempelvis, at der var forskel på beregnere og matematikere. Mens hans samtids beregnere var en slags matematiske assistenter, der blot slavisk udførte de stillede regneopgaver, besad uddannede matematikere en ubekendt kvalitet i form af intuition eller anden umiddelbar forståelse eller indsigt, og derfor ville de kunne udføre opgaver, som hverken menneskelige eller mekaniske beregnere kunne.

Turing var med andre ord overbevist om, at funktioner og tal, som anses for at være uberegnelige med en computer (menneske eller maskine) efter en mekanisk forskrift (program), kunne beregnes af en matematiker,
der prøvede sig intuitivt frem mellem forskellige beregningsmetoder.

Jack Copeland rejser derfor det interessante spørgsmål, om man kan overføre dette til en ny form for beregningsmaskine. Nogle forskere mener faktisk, at hjernen er en hyper-computer, og at spørgsmålet bare er, hvor godt vi kan efterligne den digitalt. Andre mener modsat, at fysikkens love forbyder en realisering af hypercomputere, fordi det vil kræve, at en uendelig mængde information skal findes inden for et endeligt afgrænset område – hvad der er umuligt.

Løberen og skildpadden

Sagen er nemlig, at hvor en almindelig computer kan udføre og færdiggøre beregninger med et uendeligt antal trin (om end kun inden for uendelig lang tid), kan en hypercomputer gøre det samme inden for et endeligt tidsrum.
Det kan illustreres med en teoretisk maskine, der virker efter det navnkundige ”Zenons paradoks”, måske bedre kendt som historien om Achilleus og skildpadden, der skulle løbe om kap med et forspring til skildpadden. Ifølge paradokset vil Achilleus aldrig kunne indhente endsige overhale skildpadden. For hver gang Achilleus nåede hen til skildpadden, var den kommet et stykke længere frem.

På samme vis vil en hypercomputer kunne foretage sin første beregning på f.eks. 1 minut, sin anden beregning på 0,5 minut, sin tredje på 0,25 minut osv. I alt vil en sådan computer altså kunne foretage et uendeligt antal beregninger inden for 2 minutter. Man kan også sige, at for så vidt vi antager, at den seneste beregning altid er rigtig, vil maskinen undervejs kun kunne lave et endeligt antal fejl, mens vi vil ende med at have det korrekte svar, hvis vi er i stand til at afgøre, om det er korrekt.

Uberegnelige størrelser

Et godt eksempel på et matematisk problem, der ikke kan beregnes, er faktisk hypercomputeren selv. I realiteten kan vi jo bare bygge en almindelig computer og rent matematisk bevise, at den i virkeligheden er en hypercomputer, selv om den ikke er.

Problemet er bare, at vi af den grund stadig ikke ved, hvordan en hypercomputer kan konstrueres, eller om den slet og ret overhovedet kan konstrueres. Så vores bevis for, at vi har bygget den, er absurd og derfor ikke noget bevis. Beviset ophæver så at sige sig selv.

Et andet eksempel på en funktion, der ikke kan beregnes, kendes også som ”den sidste, der kommer ind, lukker døren”. Hvem det skal være, kan ikke beregnes, for ingen ved, hvor mange personer, der egentlig kommer ind. Og fastsætter du et antal, ved stadig ingen, hvem der bliver den sidste. Kun ved også at fastsætte rækkefølgen er der en løsning, men så er der til gengæld heller ikke noget problem.

Man kan sige, at begge problemer så at sige ”bider sig selv i halen”, og det er netop det, der gør dem uberegnelige. Hvis spørgsmål af denne type præsenteres for en traditionel computer, vil det give sig udslag i det såkaldte ”halting problem”. Den vil enten køre i ring i al evighed eller gå i stå. En computer efter Turings opskrift kan ikke forudberegne, om et beregningsproblem vil ende med det ene eller det andet. Men en hypercomputer vil – i hvert fald i teorien – ud fra et givet program og givne oplysninger kunne forudberegne beregningen gennem et uendeligt antal trin og derved afgøre, om problemet vil afstedkomme det ene eller det andet.

Det forudsætter dog, at computeren både har ubegrænset hukommelse og tid til rådighed.
Så stadig bølger diskussionerne højt om, hvorvidt en hypercomputer i realiteten nogensinde vil blive andet end et abstrakt begreb, og hvad der egentlig stiller sig i vejen for at konstruere en hypercomputer. En af de ting, der i hvert fald vil adskille hypercomputere fra supercomputere er, at hypercomputere ikke nødvendigvis vil basere sig på binære tal eller symboler, der kan udprintes på papir, eller at alle informationer nødvendigvis skal være til stede forud for deres beregninger (der heller ikke nødvendigvis behøver at følge de samme regler beregningen igennem).

Der er endnu ingen, som har bygget en fungerende hypercomputer. Men det skorter ikke på realistiske bud.

Hava Siegelmann, der i dag er professor ved University of Massachusetts i USA, offentliggjorde i 1995 tanker om et kunstigt, analogt neuralnetværk, Artificial Recurrent Neural Network (ARNN), der kunne udføre beregninger, som ikke er mulige med en digital computer. Netværket skulle være resultatet af et uendeligt antal udviklingstrin og altså fungere analogt og ikke digitalt.

Hendes artikel i Science er dog blevet mødt af kritik fra blandt andet matematikeren Peter Shor, der i dag er kendt for en algoritme, som kan få kvantecomputere til at knække krypteringer. Han anerkendte dog, at hyper-computere muligvis burde være analoge frem for digitale. Forskerne Jan van Leeuwen og Jiří Wiedermann har også slået til lyd for, at internettet kunne udvikles til et frit flydende, uensartet system, der undervejs kunne få hypercomputer-egenskaber.

For tiden arbejder blandt andet Steven Younger og Emmett Redd fra Missouri State University på at realisere Siegelmanns tanker. De mener, at analoge hypercomputere ikke er underlagt de samme fundamentale begrænsninger, som de fleste forskere mener, gælder for hypercomputere baseret på digital teknologi.

Fremtiden for hypercomputeren er med andre ord ligeså flydende som de udfordringer, computeren skal løse. Men hyperarbejdende menneskehjerner arbejder til stadighed på en løsning.

”Internet skal kunne udvikles til et frit flydende, uensartet system med hypercomputer-egenskaber.”