nicht-triviale semantische Eigenschaft

Einfache Sprache

Def. Nicht-triviale semantische Eigenschaft

Sei $L$ eine Teilmenge aus der Menge aller möglichen Kodierungen von Turingmaschinen. $L$ ist eine nicht-triviale semantische Eigenschaft von Turingmaschinen, wenn

eine TM $\mathcal M$ mit $\langle\langle\mathcal M\rangle\rangle\in L$ existiert,

eine TM $\mathcal M$ mit $\langle\langle\mathcal M\rangle\rangle\not\in L$ existiert und

für alle äquivalente TM $\mathcal M$ und $\mathcal M'$ gilt $$\langle\langle\mathcal M\rangle\rangle\in L\iff \langle\langle\mathcal M'\rangle\rangle\in L\;.$$

Semantisch? Die Eigenschaft darf sich nur auf input-ouput beziehen. Wenn also zwei Funktionen den gleichen input und output haben, dann muss die Eigenschaft für beide Wahr oder für beide Falsch sein.

Trivial? Die Eigenschaft darf nicht immer wahr bzw. falsch sein. Dann können wir die TM die auf die Eigenschaft testet nicht benutzen, da sie nutzlos ist.

$\langle\langle\cdot\rangle\rangle$? Die doppelte Klammerung soll verdeutlichen, dass es hier um eine einheitliche Kodierung von kodierten TMs geht. Da eine Eigenschaft eine Menge der Sprachen ist, die die Eigenschaft haben, und daher unendlich können wir schlecht damit arbeiten. Also nehmen wir eine kodierte TM die die jeweilige Sprache erkennt. Sei $P$ eine Eigenschaft, dann ist $L_P$ die Menge aller Kodierungen für Turingmaschinen $\mathcal M_i$ so, dass $L(\mathcal M_i)\in P$.

Home: