utm und smn Eigenschaften < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich schaue mir gerade das spezielle Halteproblem an. Dabei werden zwei Eigenschaften definiert um zu zeigen, dass das spezielle Halteproblem nicht entscheidbar ist.
1. utm-Eigenschaft (universelle Turingmaschine):
Die Wortfunktion, die Wörter w#x für w [mm] \in [/mm] {0,1} ^{*} und x [mm] \in E^{*} [/mm] auf [mm] h^{'}_{w} [/mm] (x) abbildet, ist berechenbar.
2. smn-Eigenschaft (Projektion):
Ist g: [mm] E^{*} \to E^{*} [/mm] eine berechenbare Wortfunktion, so gibt es eine totale berechenbare Wortfunktion r derart, dass für alle x [mm] \in [/mm] {0,1} ^{*} und alle y [mm] \in E^{*} [/mm] gilt:
g(x#y)= [mm] h^{'}_{r(x)} [/mm] (y)
Anmerkung: [mm] h^{'}_{w} [/mm] ist die Menge aller berechenbaren Wortfunktionen von w bei Eingabe x.
So, ich verstehe quasi nix...Habe mir andere Beweise im Internet dazu angeschaut und die sind wesentlich einfacher aufgebaut. Finde aber irgendwie keinen Bezug zu diesen beiden Eigenschaften...
Könnte mir jemand das erklären?
Danke schon mal!
Liebe Grüße
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Fr 20.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
