Berechenbarkeit (1) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 12:26 Do 16.02.2006 | | Autor: | mathiash |
| Aufgabe | Eine Menge [mm] A\subseteq\{0,1\}^{\star} [/mm] heisst
(i) rekursiv aufzählbar ((Turing-) berechenbar), falls es eine Turing-Maschine M gibt mit
[mm] A=\{x\in\{0,1\}^{\star}\: |\: M(x)\:\: hält \}
[/mm]
(ii) rekursiv ((Turing- ) entscheidbar), falls es eine Turing-Maschine M gibt, die auf jeder Eingabe [mm] x\in\{0,1\}^{\star}
[/mm]
terminiert (d.h. M ist eine totale TM) und so dass gilt
[mm] A=\{x\in\{0,1\}^{\star}\: |\: M(x)\:\: gibt \:\: 1\:\: aus\:\:\}
[/mm]
Zeige:
(1) Falls A Turing-entscheidbar ist, so ist A Turing-berechenbar.
(2) Es gibt Mengen [mm] A\subseteq\{0,1\}^{\star}, [/mm] die nicht Turing-berechenbar sind.
(3) Es gibt Mengen [mm] A\subseteq\{0,1\}^{\star}, [/mm] die Turing-berechenbar, aber nicht Turing-entscheidbar sind.
(4) Definiere das Halteproblem und das Spezielle Halteproblem K.
Zeige: Beide sind Turing-berechenbar, aber nicht Turing-entscheidbar.
(5) Zeige: [mm] A\subseteq\{0,1\}^{\star} [/mm] ist Turing-entscheidbar genau dann, wenn A und [mm] \{0,1\}^{\star}\setminus [/mm] A
Turing-berechenbar sind. |
Hallo zusammen,
dies sind ein paar Standard-Aufgaben für alle, die es mal gebrauchen können.
Fragt ruhig nach, oder besser noch: Kommt bei Problemen vorbei !!! 
Gruss,
Mathias
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:53 So 05.03.2006 | | Autor: | Bastiane |
Lieber Mathias!
Aus lauter Langeweile will ich jetzt auch endlich mal diese Aufgaben beantworten. Naja, also, ich glaube, das ist mal ganz gut, wenn ich mir das jetzt mal vernünftig aufschreibe. Ich kann's jetzt fast, vielleicht kann ich's ja nach dem Aufschreiben dann ganz.
> Eine Menge [mm]A\subseteq\{0,1\}^{\star}[/mm] heisst
>
> (i) rekursiv aufzählbar ((Turing-) berechenbar), falls es
> eine Turing-Maschine M gibt mit
>
> [mm]A=\{x\in\{0,1\}^{\star}\: |\: M(x)\:\: hält \}[/mm]
>
> (ii) rekursiv ((Turing- ) entscheidbar), falls es eine
> Turing-Maschine M gibt, die auf jeder Eingabe
> [mm]x\in\{0,1\}^{\star}[/mm]
> terminiert (d.h. M ist eine totale TM) und so dass gilt
>
> [mm]A=\{x\in\{0,1\}^{\star}\: |\: M(x)\:\: gibt \:\: 1\:\: aus\:\:\}[/mm]
>
>
> Zeige:
>
> (1) Falls A Turing-entscheidbar ist, so ist A
> Turing-berechenbar.
Konstruiere eine Turingmaschine [mm] \cal{M}' [/mm] wie folgt: Falls [mm] \cal{M} [/mm] bei Eingabe x 1 ausgibt, so soll [mm] \cal{M}' [/mm] halten, falls [mm] \cal{M} [/mm] bei Eingabe x 0 ausgibt, so soll [mm] \cal{M}' [/mm] nicht halten, also unendlich weiterlaufen.
Nur wie beschriebe ich, was [mm] \cal{M} [/mm] ist? Kann man da sagen: [mm] \cal{M} [/mm] ist die Maschine, die A entscheidet???
> (2) Es gibt Mengen [mm]A\subseteq\{0,1\}^{\star},[/mm] die nicht
> Turing-berechenbar sind.
Da fällt mir gerade allerdings gar nichts zu ein... Obwohl ein Gegenbeispiel ja eigentlich reichen würde und vllt gar nicht so schwer ist!?
> (3) Es gibt Mengen [mm]A\subseteq\{0,1\}^{\star},[/mm] die
> Turing-berechenbar, aber nicht Turing-entscheidbar sind.
Nehmen wir z. B. das spezielle Halteproblem [mm] K=\{c(M)|\mbox{M hält bei Eingabe c(M)}\}. [/mm] K ist berechenbar, dann ich kann eine Turingmaschine [mm] \cal{M}' [/mm] wie folgt konstruieren:
[mm] \mathcal{M}'(c(M)) [/mm] simuliere M auf c(M) dann gilt:
M(c(M)) hält [mm] \gdw \mathcal{M}'(c(M)) [/mm] hält
Somit ist K berechenbar. K ist aber nicht entscheidbar, denn, angenommen, K wäre entscheidbar, so könnte ich eine Turingmaschine [mm] \mathcal{M_0} [/mm] wie folgt konstruieren:
falls M(x) hält [mm] (\gdw x\in [/mm] K, wobei x natürlich von der Form (Code einer Turingmaschine) sein muss), so soll [mm] \mathcal{M_0}(x) [/mm] in eine Endlosschleife gehen
falls M(x) nicht hält [mm] (\gdw x\notin [/mm] K), so soll [mm] \mathcal{M_0}(x) [/mm] (halten und) 1 ausgeben
Nun gucken wir, was passiert, wenn wir [mm] \mathcal{M_0} [/mm] die Eingabe [mm] c(\mathcal{M_0}) [/mm] geben:
1. Möglichkeit: [mm] \mathcal{M_0}(c(\mathcal{M_0}))=1, [/mm] das bedeutet nach Definition des speziellen Halteproblems, dass [mm] \mathcal{M_0}\in [/mm] K ist. Das wiederum bedeutet, dass [mm] M(c(\mathcal{M_0})) [/mm] hält, und das wiederum würde bedeuten, dass [mm] \mathcal{M_0} [/mm] in eine Endlosschleife gehen müsste [mm] \to [/mm] Widerspruch
2. Möglichkeit: [mm] \mathcal{M_0}(c(\mathcal{M_0})) [/mm] geht in Endlosschleife. Das bedeutet nach Definition von K, dass [mm] c(\mathcal{M_0})\notin [/mm] K. Das wiederum bedeutet, dass [mm] M(c(\mathcal{M_0})) [/mm] nicht hält, und das würde heißen, dass [mm] \mathcal{M_0}(c(\mathcal{M_0})) [/mm] 1 ausgibt [mm] \to [/mm] Widerspruch
Geht das Ganze eigentlich auch allgemein, also dass man keine spezielle Menge nimmt, die berechenbar aber nicht entscheidbar ist, sondern das allgemein zeigt?
> (4) Definiere das Halteproblem und das Spezielle
> Halteproblem K.
K siehe oben
[mm] HP=\{c(M,x)|\mbox{M hält bei Eingabe x}\}
[/mm]
> Zeige: Beide sind Turing-berechenbar, aber nicht
> Turing-entscheidbar.
zu K siehe oben
zu HP:
HP ist berechenbar, denn konstruiere [mm] \mathcal{M_1} [/mm] wie folgt:
[mm] \mathcal{M_1}(c(M,x)) [/mm] simuliert M auf x
[mm] \Rightarrow \mathcal{M_1}(c(M,x)) [/mm] hält [mm] \gdw [/mm] c(M,x) hält
HP ist nicht entscheidbar, denn es gilt [mm] K\le [/mm] HP folgendermaßen:
[mm] c(M)\mapsto [/mm] c(M,c(M))
und somit wäre auch K entscheidbar, wenn HP entscheidbar wäre, da wir aber gezeigt haben, dass K nicht entscheidbar ist, kann auch HP nicht entscheidbar sein!
> (5) Zeige: [mm]A\subseteq\{0,1\}^{\star}[/mm] ist
> Turing-entscheidbar genau dann, wenn A und
> [mm]\{0,1\}^{\star}\setminus[/mm] A
> Turing-berechenbar sind.
Die war schön! ![[sunny]](/images/smileys/sunny.gif "[sunny]")
Sei [mm] M_0 [/mm] die TM, die A berechnet und [mm] M_1 [/mm] die TM, die [mm] \overline{A} [/mm] berechnet (sofern man das so sagen kann), dann konstruiere ich mir eine totale TM M folgendermaßen:
[mm] M(x)=\begin{cases} 1, & \mbox{falls } M_0(x) \mbox{ hält} \\ 0, & \mbox{falls } M_1(x) \mbox{ hält} \end{cases}
[/mm]
Da x [mm] \in [/mm] A oder [mm] x\in \overline{A} [/mm] immer gilt, hält M auf jeden Fall (ist also total), und sie entscheidet A offensichtlich auch. 
So, das nochmal-Durchlesen war jetzt nur noch mit halber Kraft, denn irgendwie bekomme ich da immer einen Knoten ins Gehirn, wenn ich mich zu lange damit beschäftige.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Guten Morgen liebe Bastiane,
fleissig, fleissig. Damit hast Du schon fast mehr am Wochenende getan als ich.
> >
> > (1) Falls A Turing-entscheidbar ist, so ist A
> > Turing-berechenbar.
>
> Konstruiere eine Turingmaschine [mm]\cal{M}'[/mm] wie folgt: Falls
> [mm]\cal{M}[/mm] bei Eingabe x 1 ausgibt, so soll [mm]\cal{M}'[/mm] halten,
> falls [mm]\cal{M}[/mm] bei Eingabe x 0 ausgibt, so soll [mm]\cal{M}'[/mm]
> nicht halten, also unendlich weiterlaufen.
>
> Nur wie beschriebe ich, was [mm]\cal{M}[/mm] ist? Kann man da sagen:
> [mm]\cal{M}[/mm] ist die Maschine, die A entscheidet???
>
Ja, ganz genau.
> > (2) Es gibt Mengen [mm]A\subseteq\{0,1\}^{\star},[/mm] die nicht
> > Turing-berechenbar sind.
>
> Da fällt mir gerade allerdings gar nichts zu ein... Obwohl
> ein Gegenbeispiel ja eigentlich reichen würde und vllt gar
> nicht so schwer ist!?
>
Turing-Maschinen M kannst Du durch endliche Strings ueber [mm] \{0,1\} [/mm] codieren,
also zu M den Code [mm] c(M)\in\{0,1\}^{\star}.
[/mm]
Dann gibt es also hoechstens [mm] |\{0,1\}^{\star}|=\: |\IN [/mm] | (abzaehlbar viele) Turing-Maschinen, und da
fuer jede berechenbare Sprache eine solche existiert, gibt es also nur abzaehlbar unendich viele berechenbare Sprachen.
Aber es gibt
[mm] |P(\{0,1\}^{\star})| \: =\: |\IR [/mm] |
viele (d.h ueberabzaehlbar unendlich viele) Sprachen, d.h. Teilmengen von [mm] \{0,1\}^{\star}.
[/mm]
> > (3) Es gibt Mengen [mm]A\subseteq\{0,1\}^{\star},[/mm] die
> > Turing-berechenbar, aber nicht Turing-entscheidbar sind.
>
> Nehmen wir z. B. das spezielle Halteproblem
> [mm]K=\{c(M)|\mbox{M hält bei Eingabe c(M)}\}.[/mm] K ist
> berechenbar, dann ich kann eine Turingmaschine [mm]\cal{M}'[/mm] wie
> folgt konstruieren:
>
> [mm]\mathcal{M}'(c(M))[/mm] simuliere M auf c(M) dann gilt:
> M(c(M)) hält [mm]\gdw \mathcal{M}'(c(M))[/mm] hält
>
> Somit ist K berechenbar. K ist aber nicht entscheidbar,
> denn, angenommen, K wäre entscheidbar, so könnte ich eine
> Turingmaschine [mm]\mathcal{M_0}[/mm] wie folgt konstruieren:
>
> falls M(x) hält [mm](\gdw x\in[/mm] K, wobei x natürlich von der
> Form (Code einer Turingmaschine) sein muss), so soll
> [mm]\mathcal{M_0}(x)[/mm] in eine Endlosschleife gehen
> falls M(x) nicht hält [mm](\gdw x\notin[/mm] K), so soll
> [mm]\mathcal{M_0}(x)[/mm] (halten und) 1 ausgeben
Gut.
>
> Nun gucken wir, was passiert, wenn wir [mm]\mathcal{M_0}[/mm] die
> Eingabe [mm]c(\mathcal{M_0})[/mm] geben:
> 1. Möglichkeit: [mm]\mathcal{M_0}(c(\mathcal{M_0}))=1,[/mm] das
> bedeutet nach Definition des speziellen Halteproblems, dass
> [mm]\mathcal{M_0}\in[/mm] K ist. Das wiederum bedeutet, dass
> [mm]M(c(\mathcal{M_0}))[/mm] hält, und das wiederum würde bedeuten,
> dass [mm]\mathcal{M_0}[/mm] in eine Endlosschleife gehen müsste [mm]\to[/mm]
> Widerspruch
>
Sehr gut.
> 2. Möglichkeit: [mm]\mathcal{M_0}(c(\mathcal{M_0}))[/mm] geht in
> Endlosschleife. Das bedeutet nach Definition von K, dass
> [mm]c(\mathcal{M_0})\notin[/mm] K. Das wiederum bedeutet, dass
> [mm]M(c(\mathcal{M_0}))[/mm] nicht hält, und das würde heißen, dass
> [mm]\mathcal{M_0}(c(\mathcal{M_0}))[/mm] 1 ausgibt [mm]\to[/mm] Widerspruch
>
Perfekt !!!
> Geht das Ganze eigentlich auch allgemein, also dass man
> keine spezielle Menge nimmt, die berechenbar aber nicht
> entscheidbar ist, sondern das allgemein zeigt?
>
Ich versuch mal, einen Deiner Standard-Reaktionslaute zu simulieren:
Mmmhh,
ein aehnlicher Mechanismus, naemlich auch ein Diagonalisierungsverfahren, funktioniert, um zB
explizit eine nicht-berechenbare Sprache zu definieren.
Sei naemlich
[mm] M_0, M_1, M_2 [/mm] , [mm] M_3,\ldots
[/mm]
eine Aufzaehlung aller TM (es gibt ja nur abzaehlbar viele, s.o.), dann definiere [mm] L\subseteq\{0,1\}^{\star}
[/mm]
wie folgt:
Es sei [mm] \{0,1\}^{\star}=\{x_0,x_1,x_2,\ldots\},
[/mm]
dann definiere
[mm] x_i\in L\:\: \colon\Leftrigtarrow\:\: M_i(x_i)\:\: haelt\:\: nicht\:\:\:\: (\forall x_i\in\{0,1\}^{\star}\: [/mm] )
dann ist
[mm] L\in P(\{0,1\}^{\star})\setminus {\mathcal B}.
[/mm]
> > (4) Definiere das Halteproblem und das Spezielle
> > Halteproblem K.
>
> K siehe oben
> [mm]HP=\{c(M,x)|\mbox{M hält bei Eingabe x}\}[/mm]
>
> > Zeige: Beide sind Turing-berechenbar, aber nicht
> > Turing-entscheidbar.
>
> zu K siehe oben
> zu HP:
>
> HP ist berechenbar, denn konstruiere [mm]\mathcal{M_1}[/mm] wie
> folgt:
> [mm]\mathcal{M_1}(c(M,x))[/mm] simuliert M auf x
> [mm]\Rightarrow \mathcal{M_1}(c(M,x))[/mm] hält [mm]\gdw[/mm] c(M,x) hält
>
Ok.
> HP ist nicht entscheidbar, denn es gilt [mm]K\le[/mm] HP
> folgendermaßen:
> [mm]c(M)\mapsto[/mm] c(M,c(M))
>
> und somit wäre auch K entscheidbar, wenn HP entscheidbar
> wäre, da wir aber gezeigt haben, dass K nicht entscheidbar
> ist, kann auch HP nicht entscheidbar sein!
>
Schön.
> > (5) Zeige: [mm]A\subseteq\{0,1\}^{\star}[/mm] ist
> > Turing-entscheidbar genau dann, wenn A und
> > [mm]\{0,1\}^{\star}\setminus[/mm] A
> > Turing-berechenbar sind.
>
> Die war schön!
>
> Sei [mm]M_0[/mm] die TM, die A berechnet und [mm]M_1[/mm] die TM, die
> [mm]\overline{A}[/mm] berechnet (sofern man das so sagen kann), dann
> konstruiere ich mir eine totale TM M folgendermaßen:
>
> [mm]M(x)=\begin{cases} 1, & \mbox{falls } M_0(x) \mbox{ hält} \\ 0, & \mbox{falls } M_1(x) \mbox{ hält} \end{cases}[/mm]
>
> Da x [mm]\in[/mm] A oder [mm]x\in \overline{A}[/mm] immer gilt, hält M auf
> jeden Fall (ist also total), und sie entscheidet A
> offensichtlich auch.
>
Schön, wenn Du's schön findest.
> So, das nochmal-Durchlesen war jetzt nur noch mit halber
> Kraft, denn irgendwie bekomme ich da immer einen Knoten ins
> Gehirn, wenn ich mich zu lange damit beschäftige.
>
> Viele Grüße
> Bastiane
>
>
Liebe Bastiane, Du glaubst gar nicht, wie oft ich schon derartige Verknotungen
gespürt habe. Das gehört wohl mit zum Beruf.
Viele Grüße,
Mathias
|
|
|
|
