Eine Aussage zum Satz von Rice finden Sie auf Seite 35 von "Computational Complexity: a Modern Approach" (Arora-Barak):
Eine Teilfunktion von bis ist eine Funktion, die nicht unbedingt für alle ihre Eingaben definiert ist. Wir sagen, dass ein TM eine Teilfunktion berechnet, wenn für jedes für das definiert ist, und für jedes für das nicht definiert ist, in eine Endlosschleife geht, wenn es bei der Eingabe ausgeführt wird . Wenn ist eine Menge von Teilfunktionen, definieren wir als die Boolesche Funktion, die am Eingang 1 ausgibt, wenn eine Teilfunktion in berechnet . Der Satz von Rice besagt, dass für jedes nichttriviale die Funktion nicht berechenbar ist.
Wikipedia gibt an, dass die Sprachen der zeitlich begrenzten Maschinen EXPTIME vollständig sind. Ich gehe davon aus, dass diese Sprache ungefähr so aussieht wie akzeptiert in weniger als Schritten . Sei also ein DTM, der diese begrenzte Sprache in exponentieller Zeit entscheidet. Es scheint, als ob diese DTM eine Eigenschaft für ALLE Turingmaschinen entscheidet, daher sagt mir meine Intuition, dass der Satz von Rice eine solche Entscheidung ausschließt. Aber offensichtlich berechnet eine Gesamtfunktion.
Was fehlt mir an der Beziehung zwischen dieser Sprache und dem Satz von Rice?
Das Rice-Theorem besagt, dass Sie nichts über das endgültige Verhalten eines Programms sagen können, wenn es bis ins Unendliche ausgeführt wird - unabhängig davon, wie Sie Programme klassifizieren, gibt es zwei Programme, die zum gleichen endgültigen Verhalten konvergieren (berechnete Funktion) ) obwohl du sie anders klassifiziert hast.
Es ist jedoch wichtig, die Programme bis ins Unendliche laufen zu lassen. Um herauszufinden, was sie in den ersten Schritten tun , können Sie sie einfach für die ersten Schritte simulieren und dann beenden, um Ihr Urteil über das Verhalten des Programms abzugeben. Eine ähnliche Simulation bis unendlich funktioniert nicht, denn wenn das simulierte Programm niemals mit einer simulierten Eingabe endet, wird auch Ihr Klassifikator divergieren, anstatt eine Klassifizierung bereitzustellen.nn n
quelle
Erstens sind die Wörter in Ihrer Sprache keine Kodierungen von Maschinen, sie enthalten mehr Informationen, sodass Sie den Rice-Satz nicht direkt anwenden können. Der Satz von Rice spricht jedoch von der Unmöglichkeit, über die von einer Turing-Maschine berechnete Funktion nachzudenken (nämlich ob sie in einer Menge ). Dies ist hier nicht der Fall, da es, wie Raphael erwähnte, zwei Maschinen , die dieselbe Funktion berechnen, aber eine in Ihrer Sprache liegt und die andere nicht (hier ignoriere ich das syntaktische Problem und vergesse es die Tatsache, dass Teil der Eingabe sind). Der Punkt ist, dass die Eigenschaft, die Sie hier betrachten, mechanisch und nicht semantisch ist (die Maschinen können dieselbe Funktion berechnen, jedoch auf andere Weise).M , M ' x , nS M,M′ x,n
quelle
Der Satz von Rice besagt, dass für jede nichttriviale Menge von von Sprachen die Menge von Turing-Maschinen, die eine Sprache in unentscheidbar ist. Wikipedia sagt, dass eine bestimmte Sprache entscheidbar ist. Es gibt also keinen Widerspruch.L.L L
quelle