Dette er boka
Oppgavene i boka er lagt ut her.
Her er en liste over symboler.
Peker til kurset SLI 110.
I boka er det to deler - hver på fire kapitler
Beregnbarhet: kapitlene 3 og 4
Beskjeder til undervisning høst 2001 - sist beskjed øverst
Øvelse logikk: (Leiv Hellebø)
her kjem oppgåvene som eg vil studentane skal ha gjort til förste gruppetime i logikk:
1.1.1 Alle partalsoppgåver.
1.1.2
1.1.3
1.1.6
1.1.8
1.1.11
Dessutan vil eg gjerne at dei skal fundere litt på kva logikk er:
a) Finn fire ord eller eigenskapar som du assosierer med logikk.
b) Pröv å svare på fölgande spörsmål ved hjelp av eksempel: Kva er det rimeleg å forvente seg av logiske språk og kva kan dei hjelpe oss med?
c) Gje eit eksempel på at proposisjonal logikk ikkje har särleg stor uttrykkskraft. (Om du står fast kan du kikke i seksjon 1.2 av boka.) Dette er openberrt ein bakdel ved utsagnslogikken (= proposisjonal logikk). Kan det også vere ein fordel?
---- Eg vil dei skal gjere så mange som mogleg så lenge det ikkje tar alt for lang tid, eller det vert for vanskeleg. ----
Øvelse beregnbarhet: (Gyrd Brændeland)
Oppgavene 3.1.1 - 3.1.5 fra boka
Oppgave 1.8.3 fra Lewis og Papadimitriou . La alfabetet være a,b. Skriv regulært uttrykk for alle stringer (ord) i alfabetet som
Oppgave 2.1.3 fra Lewis og Papadimitriou . Konstruer en deterministisk endelig automat i alfabetet a,b som aksepterer ord der
Senere vil Gyrd og Leiv selv legge ut øvelsesoppgaver
Uke 35
Her er noen pekere til logikere
Frege er den som grunnla moderne logikk, og Gödel er kanskje den mest kjente logikeren. Thoralf Skolem - som var professor ved Universitetet i Oslo - hører også med til de betydligste gjennom tidene.
Det første store skillet er
I kapittel 1 skal vi konsentrere oss om logikk som språk. De to viktigste logikkene er
Her tar vi først for oss utsagnslogikk.
Hva er et utsagn? Det er en
Et konnektiv er en setningsdel som forbinder utsagn til nye utsagn - og sannhetsverdien av det nye utsagnet er bare avhengig av sannhetsverdiene av delutsagnene. Vi sier at et konnektiv er en sannhetsfunksjon. Vi vil her ta for oss følgende konnektiv
Vi er ganske brutale med hensyn til hvilke sannhetsfunksjoner de skal representere. Noen punkter der det er tatt stilling som kan være på tvers av dagligtale
Konnektivene er definert ved sannhetstabellene. Dette er helt presist. Det kan godt tenkes at vi i vår dagligtale bruker "og" "eller" "hvis" på annen måte enn som konnektiver. Men ofte kommer vi langt ved bruk av konnektiver.
Ved oversettelse til utsagnslogikk vil vi ofte se uklarheter i dagligtale, som vi må ta stilling til. Vanlige uklarheter
Så var det litt om elektriske kretser. Det var bare et eksempel på steder der utsagnslogikk anvendes. (Der snakker en ofte om Boolesk algebra i stedet for utsagnslogikk.)
Uke 36
Ved oversettelse til utsagnslogikk prøver vi å dele en setning opp i mindre deler som er knyttet sammen med konnektiver. En slik oversettelse kan ofte gi en pekepinn om uklarheter i den opprinnelige setningen. Slik skjer ofte ved oversettelse fra et mindre presist til et mer presist språk. På den annen side er det mange distinksjoner som mistes ved oversettelsen. Dette er igjen ofte noe som oppdages først ved oversettelse.
En vesentlig svakhet ved utsagnslogikk er at konnektivene er sannhetsfunksjoner. Det betyr at det er bare sannhetsverdiene av setningsdelen som spiller noen rolle. Anta f eks at vi har en lang setning, S(A), der A inngår
--------- A ----------
og en setning B som har samme sannhetsverdi som A. Og vi har setningen fått fra S(A) ved å erstatte A med B
--------- B ----------
Vi kaller den nye setningen for S(B). Da vil S(A) og S(B) ha samme sannhetsverdi. Dette gir begrensninger på hva vi kan bruke utsagnslogikk til å uttrykke - som regel er det mer enn sannhetsverdien av delene som betyr noe.
Med predikatlogikk får vi et formelt språk der det aller meste kan uttrykkes. Andre navn på predikatlogikk er
Det at predikatlogikk er så uttrykksfullt har gjort stort inntrykk på mange. Filosofen Rudolf Carnap (og Arne Næss) var en av dem
http://www.utm.edu/research/iep/c/carnap.htm
Jeg mener nok selv at han var litt naiv med hensyn til hvor praktfullt språk det var. Vår helt, Gottlob Frege, sammenlikner det med et mikroskop i forhold til øyet. Øyet er stort sett bedre til det meste, men for en del vitenskaplige formål trenger en mikroskopet.
Hva ligger det i predikatlogikk? Utover konnektivene for utsagnslogikk har vi
Hvilke ting trengte en predikatlogikk for å uttrykke? Hvis vi ser på logikkhistorien, så virker følgende klart
Gottlob Frege, med sitt "Begriffsschrift" fra 1879, løste problemet med kvantorer. Det vesentlige nye er at han innførte variable for å gjøre kvantorene begriplige. Her er et eksempel
Freges oversettelse gjør meningen med den opprinnelige setningen mye klarere.
I kap 1.2 er det slektskapsrelasjonene (filosofen Carnap var opptatt av disse) som er de vesentlige. Dere har forstått kap 1.2, når dere har forstått problemene 12, 15, 16.
Til slutt sier jeg litt om modallogikk. Det er mer for å markere et sted vi kan gå videre. Men ikke bry dere om bakgrunn 8 og problem 17 før dere har fått det andre på plass.
Uke 37
Nå er de første obligatoriske oppgavene lagt ut. Bruk denne uka til å gjøre dem og få oversettelse til utsagnslogikk og predikatlogikk på plass.
Vi ser litt på normalformer. Ved oversettelse til logikk får vi oversatt til utsagn i utsagnslogikk og predikatlogikk. Her ser vi på at vi kan beskrive nærmere formen på de oversatte utsagnene. Til nå har vi innført
Vi snakker nå videre om
Ikke noe av dette er spesielt vanskelig. Vi innfører dette for å gi oss litt flere begrep for å snakke om logiske utsagn.
Hva skal læres? Selvsagt hva formene er og kunne bruke dem til å snakke om logiske utsagn. Videre er det argumenter for hvordan vi kan oversette til en del av disse formene. De argumentene er heller ikke vanskelige. Det eneste vanskelige her er hvordan en kan argumentere presist for oversettelsen av utsagnslogiske utsagn til negasjonsnormalform. Det vanskelige er induksjonsbeviset - og kanskje hva som er vitsen med det. En kan godt skjønne hva som skjer uten å lage så mye vesen rundt det. Min mening her er: en trenger ikke induksjonsbevis for å forstå oversettelsen til negasjonsnormalform. Det er vel heller enklere å skjønne den uten at en tvinger fram denne presisjonen. Men med videre arbeid i logikk vil en måtte gjøre ting tilsvarende presist - og da er det greit å prøve denne presise behandlingen på noe som en ellers skjønner på annen måte. Mitt råd er: ikke bruk arbeid på induksjonsbeviset før en skjønner at en oppnår noe ved det. Foreløpig er det viktig å se hvordan oversettelsen gjøres - og det kan en finne ut av ved å gjennomføre noen slike oversettelser.
Altså - konsentrer dere om de obligatoriske oppgavene denne uka. Pass på at dere får til oversettelser.
Hvilke feil er de virkelige stygge ved oversettelser ?
Så kan annet også gå galt. En kan misforstå / oversette galt. Men pass på at en oversetter til noe som gir mening - til noe som er syntaktisk (grammatikalsk) riktig.
Feil i boka side 39 - midt på sida. Under 1 skal det stå "- en disjunktiv klausul". Under 2 skal det stå "konjunksjon av to disjunktive klausuler". Jeg har altså byttet om de to forklaringene.
Uke 38
Hornformler er en nyttig klasse av utsagn. I mange sammenhenger der vi bruker logikk dukker de opp. Det er ikke mye nytt stoff her - og bruk uka til å repetere kapitlene så langt.
Argumentene for at Hornformler er nyttige er to
Navnet Hornformel har ikke noe med "horn" å gjøre. De er kalt opp etter logikeren A.Horn som arbeidet med slike formler i 1950-åra ved Berkeley.
Uke 39
I kap 1.5 ser vi hvordan utsagnslogikk og predikatlogikk kan beskrives presist. Her er det noen hovedpunkter
Jeg har understreket at det er viktig å vite hvor en må være pedantisk - og hvor en ikke trenger være det. En kan få problemer med tvetydighet av uttrykk om det ikke er nok parenteser, men som regel er det klart av sammenhengen hvordan uttrykk skal forstås. Noe annet er det med signaturen. Det må være klart før det gir mening å snakke om begreper som gyldighet / falsifiserbarhet / ---- . Dette er nøkkelbegreper i logikk.
Skillet mellom logiske og ikke-logiske deler er en opplysende måte å forklare de logiske grunnbegrepene. Dette skillet går tilbake til logikeren og filosofen Berhard Bolzano (1781 - 1848). Skillet åpner for at det kan være mange ulike logikker:
Dette skillet er også viktig for å forklare forskjellen mellom sannhet og gyldighet. Dette skillet blir ofte ikke forstått. Men for oss er det klart
La oss se litt på predikatsymboler og funksjonssymboler. Vi snakker om ariteten. Det er altså antall argumenter de tar. Vi har en språkbruk som ikke svarer helt til dagligspråket
Men det vesentlige her for oss er å holde orden på om det er predikatsymbol eller funksjonssymbol - og hvilken aritet det har. Om det er et predikatsymbol, vil en ved innsetting av riktig antall termer få ut et utsagn. Om det er et funksjonssymbol, vil en ved innsetting av riktig antall termer få ut en term.
Skopet - eller rekkevidden - til en kvantor er et viktig begrep. Mye arbeid for forståelse av tvetydighet i naturlig språk har gått på å se hvordan skop til kvantorer ikke blir tilstrekkelig markert. Det kan være vanskelig å forklare presist skopregler - og spesielt regler for hvilke kvantorer som binder hvilke variable. En av de viktigste teoriene i teoretisk informatikk - lambdakalkyle - tar for seg akkurat slikt.
Så har det moret meg å ta for meg begrepet struktur - og forbindelsen til Sophus Lie. For det første er det viktig å avmystifisere "struktur" - og for det andre er det viktig å påpeke at det ikke gir mening å snakke om strukturer i sin allminnelighet. Signaturen til språket må være bestemt. En må si hvilke relasjonssymboler og funksjonssymboler som er med.
Uke 40
Igjen er det gode muligheter til å repetere hele kapittel 1. Det helt vesentlige i 1.6 er skillet mellom et knippe av begreper som forutsetter et språk (dvs en signatur) og en tolkning
og begreper som er bare avhengig av signaturen og ikke er avhengig av noen spesiell tolkning
Vi har sett tolkninger som rader i sannhetsverditabeller for utsagnslogikk. For predikatlogikk er tolkning noe som er relativt til en signatur og er gitt ved
For at dette skal bli konkret se nøye på tolkninger av språket med følgende signatur
Tolkning 1:
Tolkning 2:
Tolkning 3:
Tolkning 4:
Tolkning 5:
Gitt et utsagn F i språket vil dette være sant / usant i de forskjellige tolkningene. Vi har:
Fra de 5 tolkningene over kan vi finne utsagn som er enten oppfyllbare eller falsifiserbare. Å vise at et utsagn er gyldig eller kontradiktorisk krever mer - vi må ikke bare angi en tolkning der noe skjer, men må vise en egenskap for alle mulige tolkninger.
Uke 41
Nå skjer overgangen til "logikk som kalkyle". Før dere går i gang må dere repetere
For utsagnslogikk gir sannhetsverditabellene en kalkyle for å regne ut om utsagn er gyldige eller ei. Med sannhetsverditabellene regner vi ut de mulige sannhetsverdiene utsagnet kan ha. Vi tar for oss alle mulige kombinasjoner av sannhetsverdier for de atomære utsagnene og regner ut sannhetsverdiene for sammensatte utsagn.
Vi skal her se på en annen måte å regne ut om utsagn er gyldige. Det gjør vi ved systematisk å prøve å falsifisere utsagnet. Da er det to utganger
Vi gjør dette ved noen enkle trinn
De to utgangene i prosedyren blir så
Det er flere ting å si om denne prosedyren med analysetrær
En av de store uløste problemer i teoretisk informatikk er om en kan lage en mer effektiv prosedyre for å undersøke om utsagn er gyldige / falsifiserbare enn metoden med analysetrær. For utsagnslogikk vil en kunne finne ut av dette med prosedyrer som tar eksponensiell lang tid
En tror at det er det beste som kan gjøres, men logikere har arbeidet med i mer enn en generasjon på å vise dette uten resultat. Dette problemet blir kalt P=NP - problemet eller Cooks formodning.
Uke 42
Vi ser på analysetrær for predikatkalkyle. Dette er viktig stoff. Dere kommer helt sikkert til å bli spurt om det til eksamen. Så la oss plassere det i forhold til det andre stoffet
Vi har i predikatkalkyle kvantorer i tillegg til konnektivene. For analyse av kvantorene er det bare to tilfeller - analyse av all-kvantor og analyse av eksistens-kvantor. Men det som skjer i analysen er mer komplisert enn i utsagnslogikk. I utsagnslogikk er det bare snakk om en tilordning av sannhetsverdier, mens en falsifikasjon i predikatlogikk må også angi et univers som kvantorene skal tolkes innenfor (vi må jo si hva "for alle" og "det fins" skal være over).
Bak teorien her står tre menn
Hva er så hovedpunktene i analysen av kvantorene
Så dette høres tungt ut. Det er kompliserte begreper. Men de er knyttet til noen regnestykker - og det er bare å regne i gang og se hvordan begrepene dukker opp.
Til slutt litt om pensum. Det er tre ting som er ekstra stoff og i tillegg krever jeg ikke så mye av teorien i 2.4
Mange av oppgavene er tunge - jeg innrømmer det. Flere steder har jeg ikke kunne dy meg i å lage "morsomme" oppgaver, men der får dere vise overbærenhet.
Uke 43
Fortsetter med analysetrær. Nå ser vi på bruk av funksjonssymboler.
Vi har brukt en åpen grein i analysetreet til å finne en falsifikasjon. Det omvendte er kanskje vel så viktig - vite hvordan en fra en falsifikasjon kan finne en åpen grein der alle utsagnene i greinen blir falsifisert.
Uke 44
Fortsetter med analysetrær. Ser også på sekvenskalkyle. Det er slik analysetrær forekommer i litteraturen. Det fins tre ulike former for systemer for logikk
To av de tre systemene er altså lagd av tyskeren Gerhard Gentzen rundt 1935. Det siste var det første som ble lagd - av Gottlob Frege i 1879.
I datafag er det mye arbeid med automatisering av utledninger. Da er det analysetrær - eller enklere varianter av det som blir brukt. Vi ser også at analysetrærne kan effektiviseres
Men slik effektivisering fører oss langt utover våre ting nå.
Uke 45
Avrunding av teorien. Viser kompletthetsteoremet. Vi har to deler
Uke 46
Repetisjon.
Uke 34
Den store personen her er Alan Turing. Dere kan lese mer om han på http://www.turing.org.uk/turing/.
Turing lagde turingmaskinen som vi skal behandle i kapittel 4. Men også automatene i kapittel 3 ligger nær opp til det han var interessert i.
Hva så med automater? Mer presist snakker vi om deterministiske, endelige tilstandsautomater. Men kort - automater. Hvilke ting fra dagliglivet svarer til en automat?
Vi tenker oss en maskin med input som blir gitt, og som svarer med aksepter / ikke-aksepter. For at dette skal kunne behandles presist gjør vi noen forutsetninger
De vesentlige forutsetningene er at vi har en oppdeling av tiden, at inputalfabetet er endelig og at vi har et endelig antall tilstander. Dette er forutsetninger som vi kunne uttrykke ved at en automat er en digital maskin.
En kan misforstå hva en tilstand er. En datamaskin er en automat. Men om vi åpner lokket kan vi ikke se tilstandene. Det er ikke delene av maskinen som er tilstandene. Vi vil heller snakke om hvilke mulige konfigurasjoner delene er i - og da er det konfigurasjoner som svarer til tilstander.
Ved å bruke tilstandsdiagram har vi en måte å anskueliggjøre (små) automater.
Legg merke til at vi både har regulære uttrykk og tilstandsdiagram. De gir to måter å betrakte automater på
Dette dobbelte perspektivet språk / maskin vil være viktig i mye av det vi gjør i kurset.
De regulære uttrykkene er viktige for
Uke 35
Først litt oversikt over de vanskelige delene i kap 3.1. Ikke ta dem før dere er sikre på det andre
Hva skal dere så lære først i kap 3.1 ?
Vi har en dobbeltholdning til tilstandene i en endelig automat
Ved å bruke tilstander og tilstandsdiagram til å beskrive automater beveger vi oss vekk fra de konkrete maskinene automaten skulle representere. Vi kan i stedet legge vekt på at et inputord lager en vei gjennom tilstandene. Så er det spørsmål om hvilke veier som fører oss mellom hvilke tilstander - og spesielt fra starttilstanden og til en aksepterende tilstand. Vi legger merke til
Slik er det for deterministiske automater. Når vi bare ser på inputord som noe som lager veier i tilstandsdiagram, blir det naturlig også å snakke om ikke-deterministiske automater. Da har en ikke en entydig vei. Slike ikke-deterministiske automater tillater mer med pilene mellom tilstander
Det gir god mening å snakke om ikke-deterministiske automater når vi snakker om automater som en mekanisme for fra inputord å lage veier gjennom tilstandsdiagrammet. Det er vanskeligere å gi dette mening når vi tenker på en automat som en konkret maskin.
For ikke-deterministiske automater D trenger vi bestemme oss for hva det vil si at et ord w blir akseptert av D. Situasjonen er altså slik at ordet w kan gi opphav til flere veier fra starttilstanden gjennom tilstandene i D. Ordet w blir akseptert av D om minst en av veiene w gir opphav til ender i en aksepterende tilstand.
Vi hadde egentlig bare to muligheter for akseptering i en ikke-deterministisk automat - enten alle veier akseptert eller at minst en av dem er det. Vi velger det siste. (Det første hadde også vært mulig, men er ikke det vi - og alle andre - har valgt.)
Det er så en viktig konstruksjon gitt i problem 40. Der viser vi hvordan vi kan fra en ikke-deterministisk automat N kan konstruere en deterministisk automat D som gjør det samme. Lær dere den konstruksjonen. Da tar vi utgangspunkt i tilstandene Q fra N. Som tilstander for D tar vi alle mulige kombinasjoner av tilstander fra Q (alle delmengder av Q). Konstruksjonen er ikke spesielt vanskelig - du får den til ved å bruke litt tid.
Og så har vi transdusere. En automat kan sees som en mekanisme som har et endelig inputalfabet og gir som output JA/NEI. Med transdusere utvider vi outputalfabetet til å kunne ha me enn 2 tegn. Vi har valgt en grei måte å gjøre det på. Det er ikke noe spesielt vanskelig med transdusere - de bare produserer mer output.
Med det er vi ferdig med kap 3.1 og starter med de kontekstfrie språkene neste uke. Vi kommer litt tilbake til automatene i kap 3.5
Uke 36
Kontekstfrie språk. Dette er kanskje den viktigste gruppen av formelle språk. De brukes til å beskrive programmeringsspråk og til å beskrive naturlige språk. På en måte er de akkurat så kompliserte at en kan beskrive interessante ting, og så lite kompliserte at en kan utføre interessante regnestykker på dem. De er bare litt mer kompliserte enn de språkene vi kan beskrive med endelige tilstandsautomater.
I datafag brukes de til å beskrive programmeringsspråk. Jeg starter med et eksempel - beskrivelsen av utsagn i utsagnslogikk. Der har en
I datafag skrives grammatikken for utsagnslogikk for det første ved
Prop = Atomær-prop | - Prop | (Prop & Prop)
Dette kan leses som
Ethvert utsagn er enten
Deretter skriver vi
Atomær-prop = p | q | r
som sier at et atomært utsagn er enten p eller q eller r
Legg merke til hvor oversiktlig og kompakt skrivemåten kan gjøres.
Denne måten å beskrive språk på i datafag kom rundt 1960 - samtidig med at det samme ble utviklet i lingvistikk av Noam Chomsky og andre.
Så sier jeg at disse skrivemåtene er en forkortet skrivemåte for kontekstfrie språk. Der har vi
Jeg har i boka skrevet grammatikken for utsagnslogikk på en slik form - dvs som en mengde av omskrivingsregler - det blir 6 regler i alt.
Så kommer vi til utledninger av ord. Det er en oversiktlig måte å se hvordan vi kan skrive om et hjelpetegn til et ord bygd opp av terminale tegn. Med et trediagram av utledningen blir det enkelt å se hva som foregår. Vi kaller et slikt tre for et parsingtre. Disse beskriver på en oversiktlig måte strukturen i utledningen.
I lingvistikk (og i datafag) er en opptatt av flere ting med hensyn til en kontekstfri grammatikk
Så
Uke 37
Vi introduserer stakkautomater. La oss plassere dette i en større sammenheng. Vi har innført endelige tilstandsautomater. De beskriver på en fullstendig måte endelige diskrete maskiner med JA / NEI som output. Med transdusere kan vi ha et endelig outputalfabet. Flott.
Det er mye en endelig tilstandsautomat ikke kan gjøre. Senere skal vi se at den ikke kan sjekke parentesuttrykk. Men parentesuttrykk er lett å behandle for maskiner og mennesker. Vi kan skrive dem opp i en kontekstfri grammatikk ved
Terminaler: ( )
Ikke-terminaler: P
Start: P
Regler:
P -> (P)
P -> PP
P -> ()
Hvis vi prøver å lage en endelig tilstandsautomat for slike uttrykk får vi problemer. Senere skal vi vise at dette er umulig.Men vi kan gjøre det med en automat som gjør noe mer enn å huske et på forhånd gitt endelig antall tilstander. Dette "noe mer" er stakken i en stakkautomat. Hvis vi tenker oss turingmannen som sjekker parentesuttrykk, så får vi lett til en algoritme om vi kan skrive litt på en kladd. Kladden svarer til en stakk.
En stakk startet som et teknisk uttrykk i student-kafeteriaverden. Stakken er stabelen med brett ved siden av kjøpedisken. Med en slik stabel kan vi gjøre følgende:
Lær deg hvordan stakkautomaten for parentesuttrykk virker. Dette er ikke så vanskelig. Tenk etter hvordan dette går utover det en kan gjøre med endelige tilstandsautomater. Videre er det ikke så vanskelig å vise at enhver kontekstfri grammatikk kan beskrives med en stakkautomat. Det omvendte - enhver stakkautomat kan beskrives som et kontekstfritt språk er vanskeligere - men er også sant. For stakkautomater er forholdet mellom deterministiske og ikke-deterministiske automater mye vanskeligere enn for endelige tilstandsautomater. Våre stakkautomater og kontekstfrie språk er ikke-deterministiske.
Feil - stakkautomaten på side 117. I teksten har jeg understreket at stakkautomater leser inputordet fra høyre mot venstre, men stakkautomaten for å sjekke parentesuttrykk har jeg beskrevet som om jeg leste uttrykket fra venstre mot høyre. Automaten blir riktig om en bytter om ( og ). Dere vil se andre steder der jeg ikke helt er konsekvent med hvordan input skal leses. Så vær oppmerksom.
Uke 38
Denne uka er igjen preget av repetisjon og arbeid med obligatoriske oppgaver. Som nytt stoff har vi hvordan vi kan bruke logikk til å simulere automater. Dette er ikke noe vanskelig - noen oppgaver viser enkelt hvordan det gjøres. Så skriv ned først noen enkle tilstandsautomater - med 2,3,4 tilstander - og deretter de logiske utsagnene som simulerer dem.
I boka har jeg valgt å gjøre notasjonen for termer (i de logiske utsagnene) og ord (som input til automatene) mest mulig like. Dette gjør at argumentasjonen skrives på en enkel måte, men kan gjøre det litt mer problematisk å skjønne hva som foregår. Ta og løs oppgavene over der dere bruker inputalfabet a,b og termer bygd opp av konstant k og unære funksjoner f, g.
Etter at dere har sett hvordan simuleringen av automater kan gjøres er det enkelt å utvide simuleringen til ikke-deterministiske automater, stakkautomater - og i neste kapittel til turingmaskiner.
Uke 39
I kap 3.5 trapper vi opp presisjonen. Ta dette som en ny repetisjon av automater. Løs oppgaver, skriv og regn. Bruk mye tid på automater med 3,4 tilstander. Få dem til å virke. Les så de første delene på nytt - og løs gamle oppgaver.
Vi skal konsentrere oss om to viktige argumenter
Disse to skal dere kunne ordentlige. Så er det annet som dere skal først jobbe med etter at dette er skjønt
Jeg kommer til å si noe om resultater:
men lar argumentene bare bli antydet.
Kap 3.6 - om Thue ordet tar vi enkelt. Vi bare innfører ordet, men viser ikke noe om det. Detaljene står i boka - og er bare for de nysjerrige.
Med det blir vi ferdige med kap 3. Hovedpunktene var
Dere skal kunne
Ting som blir skjøvet litt ut - og bare er for de mer interesserte
Uke 40
Turingmaskiner! Det er på tide å se ordentlig på siden http://www.turing.org.uk/turing/.
Alan Turing gjorde flere ting
Vi skal
Jeg tror det er fornuftig å arbeide med noen enkle turingmaskiner. Ikke gi dere før dere forstår
Uke 41
Videre arbeid med turingmaskiner. Konsentrer dere om å se hvordan parentessjekkeren virker - og så lage varianter
Deretter konvertererne mellom unære og binære tall. Grunnen til at vi arbeider med tall er ikke at vi skal drive tallregning på turingmaskinene, men at tallregning kan sees som en form for symbolbehandling. Tenk på addisjon av tall - vi utfører det ved en manipulering av ord bygd opp fra tegnene 0,1,2,3,4,5,6,7,8,9. Med bokstavtekster bruker vi kanskje de 29 symbolene a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,æ,ø,å. Da kan vi av og til ha moro å se et bokstavord som et tall i 29-tallsystemet.
Så litt om hva som er det viktige pensumet - det dere helt sikkert blir spurt om og skal beherske.Og om det som dere skal konsentrere dere om etter at det andre er forstått. Her kommer en liste over ting som dere bør utsette
Så til listen over ting som dere må kunne
Dette vil være det vesentlige som dere blir spurt om til eksamen.
Uke 42
Videre arbeid med turingmaskiner. Vi ser på flittige bevere. Formålet er todelt
Argumentet for det siste er ikke helt tilfredsstillende slik det står i boka. Men det lar vi være. Et bedre argument er knyttet til stoppeproblemet og argumentet som går via universelle turingmaskiner. For dere er de flittige beverne en invitt til oppgaver.
Forbausende lite er kjent om beverfunksjonen. Av det som står i boka finner en at
B(1)=0
B(2)=0
B(3)=1
B(4)=3
Men så vet jeg ikke om flere tall. Jeg går ut fra at jeg kan finne ut hva B(5) - og kanskje B(6) er, men så regner jeg med at det er slutt. Å finne f eks B(10) er hinsides hva vi klarer å få til.
Uke 43
Den universelle turingmaskinen.
Den simulerer beregninger av turingmaskiner i alfabetet 0,1. Dette er ikke noen begrensing - vi kan tenke på en hvilken som helst beregning som utført av en turingmaskin i alfabetet 0,1.
For en regning på en vanlig turingmaskin så trengs
I en universell turingmaskin blir tapen brukt til mer
- og så vil den universelle turingmannen kunne utføre en hvilken som helst beregning så snart han får oppgitt
Dere skal kunne se at ideen om en universell turingmaskin er en robust ide. Den kan realsieres på mange ulike måter - og enhver rimelig måte vil virke like bra. I boka er en ytterst elegant universell turingmaskin av Stål Aanderaa beskrevet. Det er ikke noe krav om at dere skal forstå beskrivelsen - men det er jo en veldig elegant og morsom maskin.
Uke 44
To temaer
En spissfindighet er bruken av "avgjørbart". Det er et krav for at et problem skal være avgjørbart at gitt en input, så skal beregningen stoppe opp etter en tid med ett av to mulige svar - JA eller NEI. Problemet med analysetrær i predikatlogikk er at beregningen ikke er garantert å stoppe opp.
For å vise at gyldighet er ikke avgjørbart så må vi simulere beregninger med logikk. Egentlig er dette rett fram - selve simuleringen skjer på samme måte som vi simulerte automater med logikk. Og så viser vi at om gyldighet kunne avgøres, så ville vi også kunne avgjøre stoppeproblemet. Men det kan vi jo ikke. Dermed kan vi heller ikke avgjøre gyldighet.
Uke 45
Repetisjon