Implementere en Turingmaskin og visualisere Busy Beavers

Introduksjon

I denne oppgaven skal dere lage en simulator for en Turingmaskin i turing.py, og et lite pygame-program i turing_pygame.py som tegner hva maskinen gjør steg for steg. Når simulatoren virker skal dere kjøre tre berømte maskiner, de såkalte Busy Beavers, og se hvor lang tid de bruker på å bli ferdige.

Kort om Turingmaskiner

En Turingmaskin ble foreslått av Alan Turing i 1936 som en enkel modell for hva det vil si å regne ut noe. Til tross for at den er svært enkel kan den utføre alt en moderne datamaskin kan. Den består av:

1. Et bånd (tape) som er delt inn i celler. Hver celle inneholder et symbol. Båndet er uendelig langt i begge retninger, og alle celler starter med symbolet 0.
2. Et lese-/skrivehode som står over én celle av gangen.
3. En liste med tilstander. Maskinen er alltid i nøyaktig én tilstand, og starter i den første.
4. Regler. Hver tilstand har én regel for hvert symbol den kan lese. En regel sier tre ting: hvilket symbol som skal skrives, om hodet skal flytte seg til venstre, bli stående eller flytte seg til høyre, og hvilken tilstand maskinen skal gå til videre.

Ett steg fungerer slik:

1. Les symbolet under hodet
2. Finn regelen i nåværende tilstand for dette symbolet
3. Skriv symbolet fra regelen til cellen
4. Flytt hodet
5. Gå til neste tilstand (eller stopp hvis det ikke er noen neste tilstand)

Kort om Busy Beavers

Hvis vi lar en Turingmaskin ha et fast antall tilstander og bare symbolene 0 og 1, finnes det bare et endelig antall ulike maskiner. Noen av dem går i løkke for alltid, men andre stopper. Av dem som stopper kan vi spørre: Hva er det lengste en maskin med n tilstander kan jobbe før den stopper? Maskinen som klarer dette kalles den travleste bveren (Busy Beaver) for n tilstander.

Tallene vokser ekstremt raskt. Funksjonen er faktisk ikke mulig å regne ut for vilkårlig n, siden den vokser raskere enn alle funksjoner vi kan programmere. Verdien for 5 tilstander ble ikke bevist før i 2024, og for 6 tilstander er rekorden en maskin (se under) som stopper etter et ufattelig stort antall steg. Om den er den travleste mulige, vet vi ikke. For en maskin med 5 tilstander vet vi at det maksimalet antallet steg maskinen kan bruke er litt over 47,2 millioner steg.

Ps. I den orginale formuleringen av en travel bever så man etter det maksimale antallet 1ere som ble skrevet, ikke antallet steg. Det finnes forskjellige versjoner av funksjonen, men felles for dem alle er at det er umulig å konstrure en algoritme for å regne seg frem til verdiene.

Reglene

Hver maskin er skrevet som en tabell. Tilstandene heter A, B, C, ... og A er starttilstanden. Hver celle i tabellen skal leses som skriv-flytt-neste: 1RB betyr «skriv 1, flytt til høyre (Right), gå til tilstand B». 1LA betyr «skriv 1, flytt til venstre (Left), gå til tilstand A». H betyr at maskinen stopper (Halt).

3 tilstander

4 tilstander

5 tilstander

6 tilstander

Denne maskinen har seks tilstander, A til F. Her er H fortsatt stopp.

Dette er den beste kjente maskinen med seks tilstander, altså den nåværende rekordholderen for Busy Beaver med 6 tilstander. Den stopper til slutt, men etter et så ufattelig stort antall steg at det aldri kan simuleres ferdig, uansett hvor rask datamaskinen er. Etter 10 millioner steg har den ikke stoppet, og båndet har da 4 098 celler.

Gitte klasser

Disse to klassene er gitt, og skal legges øverst i turing.py. Konstanter gir navn til retningene, slik at dere slipper å bruke tallene -1, 0 og 1 direkte. Regel samler de tre tingene en regel består av i navngitte felt.

class Konstanter:
    VENSTRE = -1
    STAA    = 0
    HOYRE   = 1


class Regel:
    """
    Hva maskinen gjør når en tilstand leser et bestemt symbol.
    """

    def __init__(self, skriv, flytt, neste):
        self.skriv = skriv   # symbolet som skrives
        self.flytt = flytt   # Konstanter.VENSTRE, STAA eller HOYRE
        self.neste = neste   # indeksen til neste tilstand, eller None for å stoppe

Klassegrensesnitt

Dere skal implementere resten av klassene i tabellen under.

Egenskaper som hode, origo, celler, tape, ferdig og steg_teller er vanlige metoder skrevet med @property, slik at de brukes uten parenteser: maskin.ferdig.

class Eksempel:
    def __init__(self, data):
        self._min_data = data
    
    @property
    def min_data(self):
        # Nå kan metoden kalles som eks.min_data, uten parentes, uten at man kan skrive til dette feltet.
        # Hvis man skriver: 
        # eks.min_data = ny_data  -> Dette gir en feilmelding.
        return self._min_data

eks = Eksempel("hei")
print(eks.min_data)     # -> hei
eks.min_data = "verden" # -> Error, objektet har ikke dette feltet

from turing import Turingmaskin, Tilstand, Regel, Konstanter

V, H = Konstanter.VENSTRE, Konstanter.HOYRE

# En maskin som legger til en ener på slutten av en rekke enere
tilstander = [Tilstand({1: Regel(1, Konstanter.HOYRE, 0), 0: Regel(1, Konstanter.STAA, None)})]
maskin = Turingmaskin(tilstander, 2)
print(maskin.kjor([1, 1]))     # [1, 1, 1]
print(maskin.steg_teller)      # 3

Del 1: Båndet

1. Implementer Celle og Tape.
2. flytt må utvide båndet når hodet går utenfor. Hvis hodet går til venstre for første celle må en ny celle settes inn først. Hodets posisjon blir da fortsatt 0, så hold rede på hvor mange celler som er lagt til på venstre side (origo). Dere trenger dette i visualiseringen for å vite hvilken celle som er startcellen.
3. Test at flytt(Konstanter.VENSTRE) fra første celle gir en liste med to celler, og at hodet fortsatt står over den nye cellen.
4. Lag metoden skriv_ut i Tape. Den skal skrive båndet til terminalen på én linje, med symbolene etter hverandre. På linjen under skal det stå en ^ rett under cellen hodet står over. Et bånd med tre celler og hodet over den midterste skrives altså slik:

011
 ^

Del 2: Tilstander og maskin

1. Implementer Tilstand.
2. Implementer steg som beskrevet i introduksjonen. Husk å sende med indeksen til nåværende tilstand når dere skriver til båndet.
3. Implementer kjor. Den skal nullstille maskinen, laste båndet og kjøre steg til maskinen er ferdig, eller til maks_steg (48 millioner) er nådd. Skriv en advarsel hvis grensen ble nådd.
4. Kjør maskinen med 3 tilstander. Den skal stoppe etter 21 steg med 5 enere på båndet. Kjør så maskinen med 4 tilstander som skal stoppe etter 107 steg med 13 enere.
5. Skriv ut båndet for hvert steg, slik at dere kan følge maskinen i terminalen. Kall skriv_ut før første steg og etter hvert steg:

maskin = Turingmaskin(tilstander, 2)
maskin.tape.skriv_ut()
while not maskin.ferdig:
    maskin.steg()
    maskin.tape.skriv_ut()

For 3-tilstandsmaskinen skal de første stegene se slik ut:

0
^
10
 ^
11
^
01
 ^
01
^
11
 ^

Sammenlign med tabellen for hånd. Hva skjer når hodet går ut til venstre for båndet? 6. Bygg maskinen med 5 tilstander og kjør den uten animasjon og uten utskrift per steg. Den skal stoppe etter 47 176 870 steg med 4 098 enere. Hvor lang tid tok det? Hvor mange celler har båndet til slutt?

Tips: Bruk navn i stedet for tall når dere lager maskinene. Da blir koden mye lettere å lese og feilsøke:

TOM, EN = 0, 1
A, B, C = 0, 1, 2
V, H = Konstanter.VENSTRE, Konstanter.HOYRE

tilstander = [
    Tilstand({TOM: Regel(EN, H, B), EN: Regel(EN, H, None)}),   # A
    Tilstand({TOM: Regel(EN, V, B), EN: Regel(TOM, H, C)}),     # B
    Tilstand({TOM: Regel(EN, V, C), EN: Regel(EN, V, A)}),      # C
]

Del 3: Visualisering med pygame

Lag turing_pygame.py som viser hva maskinen gjør. Båndet tegnes som én rad med farger, og en pil under raden peker på cellen hodet står over. Båndet står stille mens pilen beveger seg frem og tilbake. Hver celle har fargen til tilstanden som sist skrev til den, og vi ser bare farger, ingen tall.

Disse konstantene er gitt:

KOLONNER = 31                   # antall celler som vises i bredden
CELLE    = 30                   # størrelsen på en celle i piksler
MARGIN   = 20                   # luft rundt båndet
PIL      = 30                   # plass til pilen under båndet
STEG_MS  = 300                  # millisekunder mellom hvert steg
KANT     = 6                    # båndet ruller når hodet er nærmere enn så mange celler fra kanten

BLAA    = (80, 170, 230)
ROED    = (230, 80, 80)
GROENN  = (110, 200, 110)
GUL     = (240, 190, 60)
ORANSJE = (240, 130, 50)
LILLA   = (160, 100, 200)

FARGER   = [BLAA, ROED, GROENN, GUL, ORANSJE, LILLA]   # én farge per tilstand
USKRIVET = (235, 235, 235)      # celler ingen tilstand har skrevet til
SVART    = (0, 0, 0)            # fargen på pilen

1. Lag funksjonen tegn(skjerm, maskin, vindu). vindu er posisjonen til cellen lengst til venstre, regnet fra startcellen (cellen båndet startet med). For hver celle i maskin.tape.celler er kolonnen i - tape.origo - vindu. Hopp over celler som havner utenfor 0 <= kolonne < KOLONNER.
2. Tegn en firkant på CELLE ganger CELLE piksler for hver celle. Fargen er FARGER[tilstand % len(FARGER)], eller USKRIVET hvis ingen tilstand har skrevet til cellen.
3. Tegn en markør (En pil kan f.eks tegnes med pygame.draw.polygon) under cellen hodet står over. Hodets posisjon regnet fra startcellen er tape.hode - tape.origo.
4. Lag funksjonen kjor(maskin) som viser vinduet og kjører ett steg per STEG_MS millisekund til maskinen er ferdig. La vindu starte på -(KOLONNER // 2), slik at startcellen er i midten.
5. Båndet må rulle hvis hodet nærmer seg kanten, ellers forsvinner pilen ut av bildet for maskiner som går langt (eller aldri stopper). Hvis hodet er nærmere enn KANT celler fra kanten, skal vindu flyttes mot hodet. Gjør det jevnt ved å bare flytte en andel av avstanden hver bildeoppdatering, for eksempel vindu += (maal - vindu) * 0.2. Da blir vindu et desimaltall, så cellene må tegnes med forskyvning i piksler.
6. Test med en maskin som alltid skriver 1 og flytter til høyre, og en som flytter til venstre. Pilen skal aldri forsvinne ut av bildet. Prøv også maskinen med 6 tilstander, som ikke stopper innen rimelig tid.
7. Kjør 3-tilstandsmaskinen. Ser dere hvilken tilstand som skrev hva?
8. Kjør 4-tilstandsmaskinen. Reduser STEG_MS slik at den ikke tar for lang tid.
9. Hva skjer når dere kjører 5-tilstandsmaskinen? Hvor lang tid ville animasjonen ta med STEG_MS = 300?

Tips

• Konstanter.VENSTRE, STAA og HOYRE er bare tallene -1, 0 og 1. Det er derfor flytt kan legge dem direkte til hodets posisjon.
• Bruk assert for å sjekke at et symbol er innenfor alfabetet, i stedet for raise.
• Hvis en maskin ikke stemmer med tallene over, skriv ut tilstand, symbol og regel for de ti første stegene og sammenlign med tabellen for hånd.
• Kjøring av maskinen med 5 tilstander vil ta lang tid
• Bare tegn cellene som er synlige. Hvis man tegner deler av båndet som ikke er synlig vil dette gjøre animasjonen tregere.

Utvidelser (frivillig, for de som blir ferdige tidlig)

• La brukeren trykke mellomrom for å pause, og piltaster for å gå ett steg frem eller tilbake.
• La brukeren justere hastigheten med + og -.
• Lag en maskin som øker et binærtall med én, og en som sjekker om en rekke enere er et partall. Hvor mange tilstander trenger dere?
• Lag en versjon av kjor som ikke lagrer hele båndet, men bare cellene hodet har besøkt, og sammenlign minnebruk for maskinen med 5 tilstander.
• Finn ut hvor mye raskere 5-tilstandsmaskinen blir hvis dere ikke bruker Celle-objekter, men en vanlig liste med tall.
• Kjør maskinen med 6 tilstander (tabellen over) med maks_steg = 10_000_000 og se hva som skjer. Maskinen stopper til slutt, men ikke innen rimelig tid. Se på animasjonen, og skriv ut hvor mange enere og celler båndet har etter 1 000, 100 000 og 10 000 000 steg. Vokser båndet like raskt hele tiden? Hvorfor kan vi aldri finne ut hvor mange steg maskinen trenger ved å bare kjøre den?
• Maskinen med 6 tilstander over er skrevet i formatet fra bbchallenge.org, der Z betyr stopp og tilstandene står etter hverandre: 1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE. Lag en funksjon som bygger en maskin fra en slik tekst, og prøv andre maskiner fra nettsiden.