dModLog

Endelige automater

Jeg har strikket en lille makropakke kaldet finite.mp (faktisk er det bare filnavnet, men af mangel på bedre...) sammen. Du kan se eksempler på anvendelse nedenfor:

• Filen med makroerne finite.mp
• En fil der forklarer brugen af pakken example.mp
• Eksemplerne defineret i example.mp indsat i en (minimal) .tex-fil tex ps

Når du MetaPost'er en fil, bør du gøre det med kommandoen mpost -tex=latex filnavn.mp, da der ellers vil være problemer med labels. Brug ikke xdvi til at se dit foreløbige resultat; xdvi er elendig til at vise eps-filer. Lav i stedet en .tex-fil hvori du inkluderer grafikken, og når du vil se om diagrammet bliver som ønsket køres så mpost -tex=latex filnavn.mp ; dvips filnavn.dvi. Bemærk at filerne ikke er inkluderet i dvi-filen (hvilket er en af grundene til at man ikke skal bruge xdvi), men først inkluderes når der dvips'es. Derfor er det ikke nødvendigt at LaTeX'e sin .tex-fil hver gang, da der jo allerede i dvi-filen står at den skal læse filerne filnavn.1, filnavn.2 osv.

Der mangler megen funktionalitet og customisabilitet i pakken endnu. Hvis du har specifikke ønsker til ændrede features kan du sende en mail. Bemærk at pakken er garanteret bug-fyldt; fx vil nogle af makroernes algoritmer gå helt amok hvis to cirkler skærer hinanden på en uheldig måde.

Afleveringer

Mine afleveringer ligger her ikke for at blive skrevet af, men fordi de skal tjene som eksempler på anvendelse af ovenstående.

• Min besvarelse af første afleveringsopgave tex mp ps pdf
• Min besvarelse af anden afleveringsopgave tex mp ps pdf
• Min besvarelse af tredje afleveringsopgave tex mp ps pdf
• Min besvarelse af fjerde afleveringsopgave tex mp ps pdf
• Min besvarelse af femte afleveringsopgave tex ps pdf
• Min besvarelse af sjette og sidste afleveringsopgave tex ps pdf

Universel Turing-maskine i bash

Skæbnen ville åbenbart, at jeg aldrig skulle få mig et liv. Jeg har derfor skrevet en universel Turing-maskine i bash. Jeg tror nok de primære grunde var følgende: Jeg kunne, jeg ville gerne lave noget selv som kunne teste korrektheden af min konstruktion fra aflevering 4, og så ville jeg gerne skrive noget som kunne vise en Turing-maskine på arbejde. Der findes ganske vist udmærkede færdiglavede tingester frit tilgængeligt fra det vide væv, men dels findes der jo en hob af (beregningsmæssigt ækvivalente) definitioner af hvad en Turing-maskine er, og en lige så stor hob af tilhørende universelle Turing-maskiner, så jeg ville skrive noget fra bunden som stemmer overens med Kozens definition; ie. den definition der bruges i dModLog F03. Valget faldt på bash fordi jeg ikke kan "programmere" i andet.

Maskinen består af et script kaldet turing. Programmet skal have tre, evt. fire, argumenter; syntaksen for brugen er derfor turing maskine input output [-verbose]. maskine er en fil der indeholder en beskrivelse af transitionsfunktionen. Hvis ð(q,s) = (p,t,d) (hvor q er den tilstand maskinen befinder sig i, s er det symbol der læses, p er den tilstand der skal skiftes til, t er det symbol der skal skrives, og d er enten L eller R), skal filen maskine indeholde en linje der er en mellemrumssepareret liste q s p t ±1 (+1 svarer til R, -1 svarer til L); antallet af mellemrum er underordnet så længe der er mindst ét. input er navnet på en én-linjes inputfil, hvor det der skal stå på båndet til at starte med skal læses fra. Programmet turing læser kun den første linje af filen (jeg bruger head -n 1 $input). output er en fil som turing har lov at skrive forskelligt output til; det bliver en 3-linjers fil bestående af 1) båndets indhold ved terminering 2) navnet på tilstanden som maskinen sluttede i 3) det totale antal iterationer udført af turing. -verbose kan man skrive hvis man har lyst til at se Turing-maskinen på arbejde; det viser løbende indholdet af båndet, navnet på den aktuelle tilstand samt en markør ^ der viser hvor på båndet man er. turing forudsætter følgende:

1. Starttilstanden hedder 'S', accepttilstanden hedder 'A' og rejecttilstanden hedder 'R' (uden '').
2. maskine simuleres kun så længe tilstanden ikke er 'A' eller 'R'.
3. Symbolet 'T' bruges til at markere venstre endepunkt, og kan derfor ikke bruges som en del af inputalfabetet. Symbolet '_' bruges til at markere et blanktegn (mellemrum).
4. Hvis maskinen står i en tilstand og læser et symbol, så det ikke er foreskrevet i maskine hvad der skal gøres, hoppes der til tilstanden 'R', det læste symbol pilles der ikke ved, og pegepinden bliver stående. Dette er meget nyttigt; dels som debugger, dels mens man opbygger filen maskine.
5. Man skal ikke i filen input angive tegnet 'T'; det bliver automatisk tilføjet.
6. Det er ikke specificeret i Kozen hvorvidt det er tilladt eller ej, men jeg tillader at man skriver tegnet 'T' andre steder end der hvor det står i forvejen; derved klipper man så at sige den foregående del af båndet væk (man kan i hvert fald ikke komme derhen igen, da transitionsfunktionen ikke må gå til venstre når den ser et 'T')

• Selve scriptet turing
• Et eksempel på en mulig maskine GCD
• En ikke særlig vellykket interaktiv overbygning til GCD GCD-interaktiv

Filen GCD ovenfor er en næsten tro implementation af min besvarelse af afleveringsopgave 4. Dog er der følgende forskelle:

• Jeg har erstattet á med b, da det simpelthen var nemmere at skrive. Båndalfabetet er derfor {T, _, a, b, #}
• Jeg tester ikke længere om inputstrengen er korrekt (dvs. af formen a*#a*) ved hvert gennemløb; det gøres kun én gang.
• Der er tilføjet en tilstand 17 mellem '3' og 'A', med det formål at fjerne # og lave b om til a
• "Oprydningen" ved tilstandene 15 og 16 gøres lidt mere effektivt
• Sidst, men absolut ikke mindst, er maskinen gjort total ved at fjerne en bug. Hvis man med den i min aflevering beskrevne maskine forsøger at beregne gcd(0,n) hvor n>0, looper maskinen. Dette er fikset ved tilføje en tilstand kaldet 6' mellem 5 og 6, som kontrollerer om tegnet umiddelbart til højre for T er #; og hvis det er tilfældet erstattes # med T og der hoppes til 17. Ellers gøres der bare det der ville være sket fra 6.

Euklids algoritme kører ca. i logaritmisk tid; dvs. gcd(m,n) udregnes i O(log(max(m,n))); se fx Algebra 1-noterne af Niels Lauritzen for et hint til hvordan det kan vises. Nu er én instruktion for en Turing-maskine jo ikke det samme som vi normalt mener med en instruktion/operation; bare en simpel addition eller subtraktion kræver i hvert fald lineær tid (ie. Plus(m,n) regnes normalt for én operation; dvs. konstant tid; mens additionen af de to tal på en Turing-maskine jo i hvert fald kræver at man løber mindst én gang henover båndet (alt afhængig af kodningen af heltal)). Hvis man prøver at køre GCD-interaktiv og giver fx tallene 19 og 14 som input kan man se hvor lang tid det egentlig tager. Jeg har opbygget følgende tabel over det gennemløbne antal iterationer (empiriske, ekstrapolerede data!):

Jeg kan ikke lige finde nogen generel formel for antallet af iterationer ved input (m,n)...