DM17:Supplerende noter om uafgørligheds beviser:
formålet med denne note er at give de studerende en form for kogebogsopskrift på, hvorledes man bygger et uafgørlighedsbevis op.
Lad os starte med at genkalde definition 5.4.1 fra Lærebogen:
Lad være sprog. En reduktion fra til er en rekursiv funktion som opfylder at .
Bemærk at vi kræver at er rekursiv, dvs at der findes en Turing Maskine som beregner . Dette er meget vigtigt og det betyder, at vi for at bruge en reduktion skal kunne gøre rede for, at den tilsvarende funktion faktisk kan beregnes af en turing maskine. Typisk gøres dette ved en diskution i ord af hvad den turing maskine der beregner skal kunne gøre og argumentere for at disse ting er mulige (se eksemplerne nedenfor).
Bevis: Ideen i beviset kan udemærket illustreres skematisk som vist
i Figur 1. Her er en turing maskine der omdanner
en streng til strengen . Denne streng gives
så videre til , som afgør . Heraf fås at
svarer ja på input præcis
hvis og nej ellers.
Figure: Turing maskinen afgør , forudsat at
findes.
Dvs den samlede maskine som er beskrevet i diagramform i Figur 1 har egenskaben at den altid stopper og svarer ja præcis når . Altså afgør .
Hvordan kan vi bruge Lemma 0.1 til uafgørligheds beviser?
Hvis vi kender et sprog L som er uafgørligt og kan vise at L kan reduceres til sproget L' vha en turing beregnelig funktion , så kan vi bruge Lemma 0.1 til at konkludere at sproget L' er uafgørligt, thi lemmaet siger at hvis L' er afgørligt, så er også L afgørligt, hvilket er en modstrid.
Opskrift på et uafgørlighedsbevis:
Lad K være et sprog vi ønsker at vise er uafgørligt, dvs vi vil vise at der ikke kan findes en turing maskine som givet en streng x over samme alfabet som K, kan afgøre om .
Bemærkninger:
Eksempler på uafgørlighedsbeviser.
Her følger to eksempler som er repræsentative, men selvfølgelig ikke udtømmende. Husk f.eks at Rice's sætning er et andet nyttigt værktøj, som I må bruge medmindre det eksplicit forbydes i den pågældende opgave. Husk at Rice's sætning kun kan bruges på spørgsmål som omhandler sprog for turing maskiner!
Figure 2: Skematisk beskrivelse af turing maskinen .
simulerer først M på den tomme streng. Hvis M accepterer
så (og først da!) undersøger om dens input har
længde 22. Hvis |w|=22 stopper og ellers looper den uendeligt.
Dvs
Det følger af ovenstående at hvis og kun hvis . Fra ovenstående beskrivelse af (samt lidt flere detaljer i ord om hvorledes man givet M kan lave ) er det klart at algoritmen som beregner en funktion der sender ''M'' over i strengen kan realiseres vha en turing maskine.
Figure: Konstruktionen af der afgør hvis
findes.
Den resulterende turing maskine afgør da vi har vist at hvis og kun hvis .
Bemærk at uafgørligheden af dette L også kan udledes af Rice's sætning!
Figure: Konstruktionen af der afgør hvis
findes.
Den resulterende turing maskine afgør da vi har vist at hvis og kun hvis .