Das spezielle Halteproblem < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo :)
Ich habe eine Frage zum speziellen Halteproblem. Im Prinzip möchte ich hier nur wissen, ob ich die zwei folgenden Begriffe richtig verstanden habe.
Der Beweis wird bei uns im Skript mit der utm- und smn-Eigenschaft bewiesen:
utm-Eigenschaft:
Die Wortfunktion, die Wörter w#x für w [mm] \in {0,1}^{*} [/mm] und x [mm] \in E^{*} [/mm] auf [mm] h_{w}'(x) [/mm] abbildet, ist berechenbar.
smn-Eigenschaft:
Ist g: [mm] E^{*} [/mm] --> [mm] E^{*} [/mm] eine berechenbare Wortfunktion, so gibt es eine totale berechenbare Wortfunktion r derart, dass für alle x [mm] \in {0,1}^{*} [/mm] und y [mm] \in E^{*} [/mm] gilt: g(x#y) = [mm] h_{r(x)}' [/mm] (y)
So, ich verstehe unter den Begriffen folgendes: Die utm-Eigenschaft sagt doch eigentlich nur aus, dass es eine Turingmaschine gibt, die die Codierung w für eine andere Turingmaschine berechnen kann. Mit Codierung ist gemeint, dass man die Arbeitsweise einer Turingmaschine als Code in w speichern kann.
Unter der smn-Eigenschaft verstehe ich, dass man mit gegebenem Code einer Turingmaschine M eine neue Turingmaschine M' erstellen kann, die so arbeitet, wie M.
So. Jetzt wüsste ich mal gerne was ihr dazu sagt. Habe ich das richtig verstanden?
Grüße
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 So 19.02.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
