Hallo,
für eine Übung in theoretischer Informatik soll ich Unentscheidbarkeit beweisen:
Beweisen Sie, dass die folgenden Probleme nicht entscheidbar sind (formalisieren Sie dazu zuerst die Probleme als formale Sprachen):
(a) Eingabe: Turing-Maschine M .
Aufgabe: entscheiden, ob M eine unendliche Sprache akzeptiert.
(b) Eingabe: zwei Turing-Maschinen.
Aufgabe: entscheiden, ob der Durchschnitt der von den TM akzeptierten Sprachen nicht leer ist.
Mein Lösungsansatz zu (a) ist folgender Gedanke:
Es ist unmöglich, zu entscheiden, ob eine Turing-Maschine M einen unendliche Sprache akzeptiert, da ein Nachweis - eben weil die Sprache unendlich ist - in endlicher Zeit niemals gelingen wird. Wobei mir das etwas trivial erscheint…
Das entspricht formal
Ist L(G 1 ) = Σ∗
ist das so richtig ?
Und zu (b)
(b) müsste, entspricht formal
L(G1) ∩ L(G2) = ∅?
oder?
Hier ist mir noch kein Ansatz eingefallen. Ich könnte mir vorstellen, dass es etwas mit dem Satz von Rice zu tun hat, oder über diesen beweisbar ist?
Als blutiger IT-Anfänger fühle ich mich diesen Aufgaben noch nicht wirklich gewachsen, dennoch möchte ich (am Mittwoch) zumindest einen Lösungsansatz einreichen.
Kann mir jemand auf die Sprünge helfen?
LG Majoogily