www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Informatik-Training" - Berechenbarkeit (1)
Berechenbarkeit (1) < Training < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Informatik-Training"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Berechenbarkeit (1): Grundbegriffe Rek.Theorie
Status: (Übungsaufgabe) Übungsaufgabe Status 
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

        
Bezug
Berechenbarkeit (1): Frage (beantwortet)
Status: (Frage) beantwortet Status 
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]

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]


Bezug
                
Bezug
Berechenbarkeit (1): Antwort
Status: (Antwort) fertig Status 
Datum: 06:06 Mo 06.03.2006
Autor: mathiash

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! [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. :-)
>  

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
>  [cap]
>  

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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Informatik-Training"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de