December 07, 2015
Kan man regne kan man regne

Billedet ovenfor kan være lidt svært at gennemskue, men hvis man klikker på det, kan man se at det i virkeligheden er ét meget indviklet regnestykke, der regner et nyt tal ud, ud fra tallet x. 

Regnestykket er konstrueret sådan at det i virkeligheden er en meget lille computer, der kan løse præcis én opgave: Hvis man har et en række 1-taller, f.eks. '1111', så kan computeren kopiere dem, så man bagefter har rækken '111101111'.

Det er lidt svært at se, og jeg ved det kun fordi jeg selv har konstrueret regnestykket, til helt præcis at være den computer. Ikke verdens bedste computer - men det er heller ikke det vigtige. Det vigtige er at den kan bygges

Ligesom verden er skabt af ganske få byggeklodser - alt stof er bygget af ganske få elementarpartikler, alt liv er bygget af ganske få aminosyrer - så skal der næsten ingenting til før man har bygget en computer, der i princippet kan præcis det samme som alle andre computere. Alan Turing kom op med ideen om Turingmaskinen, som et eksempel på en maskine man ikke kan være i tvivl om kan bygges, som i virkeligheden kan det hele: En tænkt maskine, der består af et bånd med symboler (bogstaver, tal) på og nogle simple regler for at flytte på båndet, skrive på båndet og læse symboler fra båndet. 
Maskinen har en bestemt tilstand, og læser fra et bestemt sted på båndet. Bestemt ud fra hvilket symbol den læser på båndet kan den nu gøre tre ting
  • Skrive et andet symbol istedet for det der stod på båndet
  • Flytte sig enten til højre eller venstre
  • Skifte til en anden tilstand
Turing beviste at man kan programmere sådan en maskine til at efterligne en hvilken som helst anden computer. Alle computere er simpelthen principielt ens - den eneste forskel på dem er hvor meget hukommelse de har, og hvor hurtige de er. 

Men - nu er jeg matematiker, og jeg synes tallene er endnu enklere end noget med et bånd og en læser og en skriver og nogen regler, så jeg bestemte mig for at lave en oversætter, der kan lave Turing-maskiner til regnestykker. Mere præcist så har jeg lavet en oversætter, der kan oversætte en maskine, der bruger tallene som symboler, til et helt almindeligt regnestykke, hvor jeg kun bruger plus, minus, gange, dividere - og som det mest mærkelige potens-opløftning, så jeg kan skrive 2^3. Det er lavet sådan at man kan køre maskinerne i Ruby, som kan regne med heltal på helt op til 300.000 cifre. 

Lige meget hvor mange år det er siden jeg lærte de her ting, så er det stadig en kilde til fascination for mig, at man i princippet kan skrive et regnestykke op, der beregner alt hvad Google gør for at returnere et søgeresultat. Hvis man havde tiden til det, kunne man faktisk bruge noget, der minder om min oversætter til at lave et gigantisk regnestykke, der - givet inputtet 'katte' omsat til et tal - returnerer en liste over alle billeder af katte i Googles indeks.

Sådan virker oversætteren

Det første problem man skal løse er at kunne se om to tal er ens. Det kan man klare ved at se om forskellen på dem er nul. Så vi skal vide om et tal x er nul. Det kan man gøre med formlen
1/(x*x+1)
hvis x er nul, så er x*x+1 = 1, så man får 1/1 - men ellers er x*x+1 større end 1, og siden vi regner med heltal, så er 1/[noget større end 1] nul.

Nu har vi sammenligning - det kan vi bruge til at lave hvis-så sætninger. Så hvis vi kalder funktionen ovenfor nul, altså nul(x) = 1/(x*x+1), kan vi skrive
nul(x)*y + (1-nul(x))*z
hvis x er nul, er nul(x) 1, så giver udtrykket y. Ellers er nul(x) nul, så går y ud, men (1-0)*z = z, så vi får z. Altså hvisellers(x,y,z) = nul(x)*y + (1-nul(x))*z

Vi kan bygge mange hvisellers udtryk sammen til at vælge et bestemt resultat ud fra om x er 1, 2, 3, 4, 5 osv... Der er flere måder at gøre det på, men f.eks.

hvisellers(x-1, 1værdi, hvisellers(x-2, 2værdi, ellersværdi)) giver
1værdi hvis x er 1, 2værdi hvis x er 2 go ellersværdi ellers.

I min oversætter har jeg valgt en lidt anden måde, hvor jeg bygger mig en meget lang form for hvisellers direkte istedet. 

Vi mangler lige et lille trick - for turing maskinen havde jo noget med en tilstand og en position og et bånd. Vi bruger et tal til at være båndet - hvert ciffer kan være et sted på båndet. Vi kan snyde lidt og skrive tilstand, position og bånd sammen i ét tal ved at reservere nogle pladser til tilstanden, nogle plader til positionen og så lade resten være båndet. F.eks. skrive tilstand 1, position 0 og bånd 111 som 
1110000001 (deles 111|00000|01| - to første cifre til tilstand, fem næste til position, resten til båndet)

nu mangler der bare nogle funktioner, der kan trække delene ud af det samlede tal og så er vi klar. Vi kan proppe tilstanden ind i en hvisellers, og vælge hvordan båndet skal se ud bagefter ved at proppe den nye værdi ind som y eller z i hvisellers-formlen.

Men hov - har jeg ikke snydt nu - med alle de funktioner jeg bruger? Ikke rigtig - for vi kan vedtage en regel, at vi erstatter funktionen med det regneudtryk den består af. Sådan at når jeg skriver 
hvisellers(1, 2, 3)
mener jeg i virkeligheden
d(1)*2-(d(1)-1)*3
og når man også erstatter d
(1/(1*1+1))*2-((1/(1*1+1))-1)*3

Det bliver hurtigt lidt indviklet - men så er det godt man kan tage en rigtig computer til hjælp til at regne formlen ud for en hel maskine: Det har jeg gjort her - du kan bruge scriptet til at regne din helt egen turingmaskinformel ud.

Posted by Claus at 12:13 PM