Reissatz für nicht-semantische Eigenschaften

Der Satz von Rice besagt , dass die einzigen semantischen Eigenschaften von Turing Machines (dh die Eigenschaften der von der Maschine berechneten Funktion), die wir bestimmen können, die beiden trivialen Eigenschaften sind (dh immer wahr und immer falsch).

Es gibt aber auch andere Eigenschaften von Turingmaschinen, die nicht bestimmbar sind. Zum Beispiel ist die Eigenschaft, dass in einer bestimmten Turing-Maschine ein unerreichbarer Zustand vorliegt, unentscheidbar . $^{\dagger}$

Gibt es einen ähnlichen Satz wie den von Rice, der die Entscheidbarkeit ähnlicher Eigenschaften kategorisiert? Ich habe keine genaue Definition. Jeder bekannte Satz, der das von mir angegebene Beispiel abdeckt, wäre für mich interessant.

$^\dagger$ es einfach ist , zu beweisen , dass dieser Satz unentscheidbar ist mit Kleenes Rekursion / Fixed Point Theoremen .

computability undecidability Kaveh
quelle

Das Halteproblem ist im Wesentlichen die Frage, ob der Haltezustand erreichbar ist, so dass die allgemeine Frage, welche Zustände erreichbar sind, mit Sicherheit unlösbar sein wird.

Carl Mummert

@ Carl, ja, das weiß ich, aber das ist anders als in meinem Beispiel. Mein Beispiel ist: Wenn Sie <M> angeben, gibt es einen Status, der nicht erreichbar ist (wenn Sie ihn entfernen, hat dies keine Auswirkung auf die Maschine bei Eingaben). Es ähnelt einer Frage in Formale Methoden: Gibt es eine unnötige Codezeile? (was normalerweise bedeutet, dass das Programm nicht wirklich wie erwartet funktioniert).

Kaveh

@Kaveh: Im Allgemeinen ist das Problem des Anhaltens Äquivalent zum Problem des Anhaltens für Maschinen, die ihre Eingabe vollständig ignorieren, und für diese spezielle Klasse von Maschinen ist das Problem des Anhaltens das Problem, ob der Anhalten-Zustand in Ihrem System erreichbar ist Sinn.

1

$1$

Carl Mummert

@ Carl, ja, ich kenne die direkte Reduktion (wir müssen sicherstellen, dass alle anderen Staaten erreichbar sind). Meine Frage bezieht sich jedoch nicht auf das Problem selbst, sondern war ein einfaches Beispiel für eine unentscheidbare nicht-semantische Sprache. Wissen Sie also, ob es etwas Ähnliches wie das Rice-Theorem gibt, das nicht-semantische Eigenschaften abdeckt? Oder halten Sie es für unwahrscheinlich, dass es einen solchen Satz gibt?

Kaveh

Reissatz für nicht-semantische Eigenschaften

Antworten: