Øvelser til uke 49
Dette er altså første uke med oppgaver etter at forelesningene er slutt, og nest siste uke med oppgaver.
Også nå tar vi oss tid til å komme a jour med eventuelle oppgaver som har blitt liggende. Forrige uke kom jeg til å gi en oppgave som likner mye på noe som står i boken. Oppgaven var imidlertid ikke identisk, og forskjellen er interessant: Eksempel 13.2 side 761 og 762 i boken beskriver en turingmaskin som aksepterer språket {a^n b^n c^n | n ≥ 0}. Begrepet akseptere, brukt om turingmaskiner, er definert nederst side 759. Finn frem denne definisjonen, og overbevis deg selv om at maskinen i eksempel 13.2 aksepterer {a^n b^n c^n | n ≥ 0}.
OPPGAVE: Gjør dette grundig, ved å skrive maskinen inn i JFLAP og prøvekjøre den på strenger både utenfor og innenfor {a^n b^n c^n | n ≥ 0}.
Hvis du ikke gjorde den aktuelle oppgaven forrige uke, så gå tilbake og se at du ble bedt om å skrive en maskin som avgjør språket {a^n b^n c^n | n ≥ 0}. Forskjellen mellom at en turingmaskin avgjør eller aksepterer et språk, er grunnleggende i beregnbarhetsteori. Generelt sier vi at en turingmaskin avgjør et problem (problem er egentlig sjargong for spørsmål) som for eksempel: er input en gyldig formel i utsagnslogikk? eller er input en gyldig formel i predikatlogikk? hvis den uansett input til slutt stopper i en av to tilstander som vi kan tolke som JA og NEI, og alltid i den riktige. Dette står omtalt rundt side 794 og 795 i pensum. Avgjøre og avgjørbart er altså norske ord for decide og decidable (evt. solvable).
Tidligere i høst så vi på metoder for å avgjøre om formler er gyldige i utsagnslogikk. Vi har også sett på metoder (stakk-automater) for å avgjøre om noe er med i språket til utsagnslogikk. Ut fra dette kan vi lage en turingmaskin som avgjør om input er en gyldig formel i utsagnslogikk. På forelesningen 22/11 skisserte jeg imidlertid et argument for at det derimot ikke fins noen turingmaskion som avgjør om input er en gyldig formel i predikatlogikk.
Avgjøre og akseptere er altså forskjellige ting, men begge er begreper vi bruker om språk i forbindelse med turingmaskiner: En turingmaskin avgjør et språk hvis den avgjør det tilsvarende medlemsskaps-spørsmålet, det vil si alltid stopper med rett svar på spørsmålet om inputstrengen er med i språket.
OPPGAVE: Vær nå helt sikker på at du forstår følgende: Hvis det fins en turingmaskin som avgjør et språk, så fins det også en turingmaskin som aksepterer det.
Like viktig er det å vite at vi ikke kan slutte i motsatt retning: Språket av gyldige formler i predikatlogikk er altså ikke avgjørbart, men det fins en turingmaskin som aksepterer dette språket. Hvorfor det? Fordi det fins et bevis-system for predikatlogikk. Vi har ikke sett på dette i detalj, men det fins. For å undersøke om en formel er gyldig, kan vi da prøve ut alle mulige beviser på en systematisk måte, og stoppe opp med et JA-svar straks vi kommer over noe som er et bevis for den aktuelle formelen. Dette tar tid, men det går an å planlegge slik at hvert eneste bevis dukker opp før eller siden hvis vi bare er tålmodige. Altså, om vi bare holder på lenge nok vil vi til slutt rope JA hvis det er det rette svaret. Alt dette får man til ved hjelp av en turingmaskin, som dermed aksepterer dette språket.
OPPGAVE: Gå tilbake til JFLAP-implementasjonen din (første oppgave ovenfor) av maskinen i bokens eksempel 13.2, og skriv den om til en maskin som avgjør dette språket.
Som forklart ovenfor er det altså slett ikke gitt at en maskin som aksepterer et språk alltid kan skrives om til en maskin som avgjør det samme språket, men i dette tilfellet er det altså mulig.
OPPGAVE 1 side 787– 788
OPPGAVE 3 side 807– 808