Satz von Rice < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich habe eine Frage zu dem Satz von Rice:
Sei R die Klasse aller Turing-berechenbaren Funktionen über dem Alphabet E. Sei S eine echte, nichttriviale Teilmenge von R.
Dann ist die folgende Sprache unentscheidbar:
C(S) = {w | die von [mm] M_{w} [/mm] berechnete Funktion liegt in S}
So, den Satz verstehe ich eigentlich schon nicht richtig. Was sagt mir das?
Dann der Beweis:
Sei S gegeben und sei ud die überall undefinierte berechenbare Funktion. Also ist ud [mm] \in [/mm] S oder ud [mm] \not\in [/mm] S.
1. Fall: ud [mm] \in [/mm] S.
Wegen S [mm] \not= [/mm] R gibt es ein q [mm] \in [/mm] R \ S.
Sei Q die TM für q.
Betrachte folgende Turingmaschine TM:
Bei Eingabe von w#x simuliert TM erst die Maschine [mm] M_{w} [/mm] angesetzt auf w. Kommt diese Rechnung zum Ende, so soll TM anschließend Q angesetzt auf x simulieren.
Und folgendes verstehe ich nicht:
Dann folgt:
- Hält [mm] M_{w} [/mm] auf w, so ist die berechnete Funktion = q
- Hält [mm] M_{w} [/mm] nicht auf w, so ist die berechnete Funktion = ud
So, erstmal bis hier hin. Wäre super, wenn mir jemand das erklären könnte. Vielen Dank!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:09 Di 27.03.2012 | | Autor: | FritzB |
Hallo liebe judithlein,
der Satz von Rice hat eine ziemlich intuitiven und sinnvollen Hintergrund: Er besagt nämlich (jetzt mal ganz frei), dass wenn eine Eigenschaft S eines beliebigen Programmes (oder einer Rechenmaschine, iPhone, Alienware Gamer PC, Supercomputer) genügend schwierig ist, dann kann es kein Programm geben, welches entscheidet, ob ein beliebiges Programm diese Eigenschaft erfüllt.
Beispielsweise sagt der Satz von Rice, dass wir kein Programm schreiben können, dem wir ein Programm als Eingabe geben und das uns dann ausgibt, ob das Programm immer den gleichen Wert ausgibt (eine konstante Funktion berechnet). Oder ob es eine andere bestimmte Funktion berechnet wie z.B. a [mm] \cdot [/mm] b, n!, ...
Wenn wir jetzt die charakteristische Funktion einer Sprache betrachten ist es auch nicht entscheidbar, ob ein Programm die leere Sprache berechnet oder [mm] \Sigma^\star [/mm] oder das Cliquenproblem in polynomieller Zeit 
Wichtig ist hierbei: Für ein festes Programm ist es nicht unbedingt schwierig zu berechnen, ob eine Eigenschaft erfüllt ist. Z.B. können wir für ein bestimmtes Programm leicht einen Algorithmus entwickeln, der uns sagt, ob das Programm Zahlen, Strings oder Bilder (etc.) ausgibt. Beim Satz von Rice sind aber die „Quantoren umgetauscht“: Es ist nicht für ein Programm ein Algorithmus zu finden, sondern ein Algorithmus, der für alle Programme entscheidet ob die Eigenschaft vorliegt.
Diese Interpretation lässt sich durch die folgenden Überlegungen erklären:
— Das „Programm“ ist eine Turingmaschine, die eine Funktion aus R berechnet. Mit der Churchschen These lässt sich der Satz von Rice dann auf alle rechnenden Maschinen (-modelle) übertragen.
— Eine Eigenschaft S können wir als Teilmenge aller rekursiven Funktionen auffassen: Alle Turingmaschinen besitzen die Eigenschaft S, wenn sie eine Funktion aus S berechnen.
— „genügend schwierig“ heißt, dass es Turingmaschinen mit dieser Eigenschaft gibt und dass nicht alle Turingmaschinen diese Eigenschaft erfüllen. Sonst wäre ein Algorithmus, der immer „Ja“ ausgibt bzw. ein Algorithmus der immer „Nein“ ausgibt denkbar.
Ich hoffe ich konnte dir damit den Satz von Rice intuitiv etwas näher bringen.
Zu deiner Frage im Beweis ein paar Gegenfragen:
1) Welche Ausgabe erzeugt denn die Turingmaschine, wenn sie hält?
2) Welche Ausgabe erzeugt eine Turingmaschine, die nie hält? Bzw. welche Funktion berechnet sie? Beachte dabei, dass eine Turingmaschine, die nie hält, tatsächlich eine berechenbare Funktion berechnet. Sogar jede nie haltende Turingmaschine die gleiche.
Viel Erfolg weiterhin! Theoretische Informatik ist ein echt spannendes Gebiet. 
|
|
|
|
