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 .

1. Vælg et sprog R som vides at være uafgørligt.
2. Beskriv en reduktion fra R til K vha en turing beregnelig funktion. Lad være en turing maskine der beregner denne reduktion. Dvs givet x beregner strengen som har egenskaben at hvis og kun hvis . Der skal redegøres for hvordan kan realiseres.
3. Lad være en hypotetisk turing maskine der afgør K (vi ønsker at vise at ikke findes).
4. Brug og som vist i Figur 1 (med ) til at lave en Turing maskine der afgør R. afgør R thi vi har argumenteret for at hvis og kun hvis .
5. Konkluder ud fra ovenstående modstrid at ikke kan findes, hvorfor K er uafgørligt.

Bemærkninger:

• Det er ikke altid oplagt hvilket sprog man skal vælge som R. Pointen er at man skal vælge noget for hvilket det kan lade sig gøre at finde en reduktion. Selvfølgelig skal man bruge egenskaber ved sproget K til at hjælpe med at vælge det rette sprog R.
  Kun træning med eksempler kan hjælpe med at blive god til denne disciplin!
• Af og til er det lettere at beskrive en reduktion af R til . Så skal man blot lade være en hypotetisk maskine som afgør . En sådan turing maskine findes hvis og kun hvis K er afgørligt, da afgørlige sprog er lukket under komplement. I nogle af mine diagrammer ved forelæsningerne bruger jeg stadig en hypotetisk turing maskine for K og bytter så om på ja og nej tilsidst (output fra den store kasse). Det er stadig iorden som bevis (selvom det er bedre at gøre som ovenfor) og I er velkommen til at gøre dette, forudsat at I stadig kan argumentere for korrektheden!

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!

• Lad . Vi viser at L er uafgørligt vha opskriften ovenfor.
  1. Lad R være (tomme strengs) haltingsproget , dvs
     . Vi ved fra Theorem 5.4.2(b) at dette sprog er uafgørligt.
  2. Lad være algorithmen som givet koden for en turing maskine M laver koden for en turing maskine som stopper på en given streng w hvis og kun hvis M stopper på den tomme streng og |w|=22. Mere præcist kan beskrives som i Figur 2.

       
     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.

  3. Antag at afgør L.
  4. Sæt og sammen som vist i Figur 3.

       
     Figure: Konstruktionen af der afgør hvis findes.
     

     Den resulterende turing maskine afgør da vi har vist at hvis og kun hvis .

  5. Konkluder at ikke kan findes og dermed at L er uafgørligt.

  Bemærk at uafgørligheden af dette L også kan udledes af Rice's sætning!

• Lad . Vi viser at Q er uafgørligt vha opskriften ovenfor.
  1. Lad igen R være (tomme strengs) haltingsproget . Vi ved fra Theorem 5.4.2(b) at dette sprog er uafgørligt.
  2. Lad være algoritmen som givet koden for en turing maskine M laver koden for en turing maskine , der gennemløber alle sine tilstande præcis hvis M stopper på den tomme streng. Dette gøres ved at lade starte med at simulere M på ved hjælp af en ægte delmængde af 's tilstande (let at realisere, tilføj blot en special tilstand der først bruges efter at M er stoppet hvis den gør det). Det er også let at sikre at en vi får gennemløbet alle tilstande f.eks ved at lave M om så den i stedet for at stoppe skriver et specielt symbol på 's bånd og så indrette således at den på symbolet fra en vilkårlig tilstand vil gennemløbe alle sine tilstande og derefter stoppe. Lad være den funktion der omdanner ``M'' til . Det er let at argumentere for at kan beregnes af en turing maskine . Vi har nu at hvis og kun hvis , thi special tilstanden vil blive gennemløbet af på input w hvis og kun hvis den vil blive det for et vilkårlig andet input w' og dette sker hvis og kun hvis M stopper på .
  3. Antag at afgør Q.
  4. Sæt og sammen som vist i Figur 4.

       
     Figure: Konstruktionen af der afgør hvis findes.
     

     Den resulterende turing maskine afgør da vi har vist at hvis og kun hvis .

  5. Konkluder at ikke kan findes, dvs Q er uafgørligt.

 
• About this document ...