?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