[informatik-bonn] Beweis zu Satz 1.7

  • From: markusdunkel@xxxxxxxxxx
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Wed, 09 Jul 2003 15:34:30 +0200

Hi Lutz,
Zu Deiner Frage wegen des Beweises von Satz 1.7:

(1) M' hält auf \psi(<M'>) <=> M auf \psi(<M'>) gibt 0 aus.
Das folgt aus der Konstruktion von M'(vgl. S.25 unten): "Falls M bei Eingabe x 
den Wert 0 ausgeben würde, dann hält M' an."
(2) M auf \psi(<M'>) gibt 0 aus <=> \psi(<M'>) \not\in H_e.
Das folgt aus der Definition von c_H_e(vgl. Def. c_L(x) S.24 oben): c_H_e = 1 
falls \psi(<M'>) \in H_e, c_H_e = 0 sonst. Wenn M auf \psi(<M'>) also 0 
ausgibt, dann ist \psi(<M'>) \not\in H_e.
(3) \psi(<M'>) \not\in H_e <=> M' hält nicht auf \psi(<M'>).
Das folgt aus der Definition von H_e(vgl. S.25):
H_e:={x \in {0,1}^+ | x=\psi(<M>) für eine TM M und M hält auf x}
Wegen \psi(<M'>) \not\in H_e kann M' demnach auch nicht auf \psi(<M'>) halten.
Et voila: der Widerspruch, dass "M' hält auf \psi(<M'>) <=> M' hält nicht auf 
\psi(<M'>)" gelten soll.
Also war unsere Annahme, dass H_e entscheidbar ist, falsch.

Hoffe, das erklärt's... (Hab's übrigens auch ins Forum gepostet)
mfg
Markus


-- 
Nur 1x anmelden
und automatisch bis zu 1200 Produktproben und Gutscheine erhalten!
http://www.freenet.de/tipp/shopping/probenking/index.html

Other related posts: