Das Problem des begrenzten Anhaltens ist entscheidbar. Warum widerspricht dies nicht dem Satz von Rice?

9

Eine Aussage zum Satz von Rice finden Sie auf Seite 35 von "Computational Complexity: a Modern Approach" (Arora-Barak):

Eine Teilfunktion von {0,1} bis {0,1} ist eine Funktion, die nicht unbedingt für alle ihre Eingaben definiert ist. Wir sagen, dass ein TM M eine Teilfunktion berechnet, fwenn für jedes x für das f definiert ist, M(x)=f(x) und für jedes x für das f nicht definiert ist, M in eine Endlosschleife geht, wenn es bei der Eingabe ausgeführt wird x . Wenn Sist eine Menge von Teilfunktionen, definieren wir fS als die Boolesche Funktion, die am Eingang α 1 ausgibt, wenn Mα eine Teilfunktion in berechnet S. Der Satz von Rice besagt, dass für jedes nichttriviale S die Funktion fS 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 {(α,x,n):Mα akzeptiert x in weniger als n Schritten } . Sei M 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 M eine Gesamtfunktion.

Was fehlt mir an der Beziehung zwischen dieser Sprache und dem Satz von Rice?

ttbo
quelle

Antworten:

13

Die Sprache

{(α,x,n):Mα accepts x in less than n steps}

ist kein Indexsatz, das heißt, er hat keine Form

LP={MM is TM, fP. fM=f}

für einen Satz von (teilweise rekursiven) Funktionen , wobei die von TM berechnete (teilweise) Funktion ist . Der Satz von Rice macht nur Aussagen über ein solches ; Viele "intuitive" Umformulierungen sind nicht hilfreich. Siehe auch hier .f M M L P.PfMMLP

Beachten Sie, dass dies hier nicht nur ein technisches Detail ist. Der Satz von Rice gilt nicht für

L={MM accepts M in less than M steps} ,

entweder. Kannst du sehen warum?

Für jede Maschine in Sie problemlos viele Maschinen erstellen, die dieselbe Sprache akzeptieren, aber für mehr als Schritte ausgeführt werden und sich daher nicht in . Somit ist kein Indexsatz.M L LLMLL

L ist entscheidbar und verwendet dasselbe Argument wie für die Originalsprache, die wir diskutieren.

Raphael
quelle
+1. Besonders für den Hyperlink, der wahrscheinlich auch hier gilt. Ich habe jedoch trotzdem versucht, eine "intuitive" Analyse als alternative Antwort beizutragen.
Jirka Hanika
6

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.nnn

Jirka Hanika
quelle
5

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 , nSM,Mx,n

Ariel
quelle
Das erste Argument ist formalistisch, aber richtig. Das zweite Argument verwirrt mich (ich bin nicht sicher, ob ich Lokalität / Globalität genau definieren kann; und ich weiß nicht, was es bedeutet, eine Funktion "aus einer Reihe von Funktionen" zu berechnen).
Jirka Hanika
Das erste Argument ist in der Tat nur syntaktisch, wie Raphael in seiner Antwort erwähnte. Das lokale / globale Problem sollte den Unterschied zwischen der Argumentation über das Ergebnis einer einzelnen Eingabe und allen Eingaben aufzeigen (ich habe es nicht im formalen Sinne gemeint, es kann etwas anderes in einem anderen Kontext bedeuten). Das Berechnen einer Funktion aus einer gegebenen Menge bedeutet einfach, dass Sie fragen, ob die von berechnete Funktion in . S.MαS
Ariel
Nach dem Rice-Theorem muss man NICHT über das Verhalten der Maschine bei allen Eingaben nachdenken. Zum Beispiel ist es unmöglich, Programme danach zu klassifizieren, ob sie letztendlich akzeptiert werden, wenn sie mit der Eingabe "5" ausgeführt werden. Oder besser gesagt, Sie können eine solche Klassifizierung definieren, die das Verhalten bei den meisten Eingaben ignoriert, aber die Klassifizierung ist immer noch nicht rekursiv.
Jirka Hanika
Dies war in der Tat verwirrend, da man als die Menge von Funktionen definieren kann, die an einem festen Eingang ausgeben . Vielen Dank, dass Sie das Problem angesprochen haben. 1S1
Ariel
3

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.LL

David Richerby
quelle