Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
56
Beweis:
ist nicht rekursiv aufzählbar
![](/pool/data/tex/20e91f25445ec781e4ad2fbcb15614ab.gif)
Reduziere eine nicht rek. aufz. Sprache auf
:
nicht rek. aufz. =>
bzw. äquivalent ![](/pool/data/tex/89bdabd6386a8c3132b4e3331c20d9fb.gif)
Konstruiere eine berechenbare Funktion f, die alle Ja/Nein-Instanzen von
auf alle Ja/Nein-Instanzen von
abbildet.
w Eingabe für![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
1.) Wenn w keine gültige GN, dann f(w)=w
2.) Wenn w=<M> GN einer TM, dann sei f(w) GN einer TM M* mit folgender Eigenschaft: M* ignoriert die Eingabe und simuliert M auf Eingabe![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
f ist offensichtlich berechenbar. Falls w keine GN ist, so gilt
und
Für w=<M> ist f(w)=<M*>:
|
=> M hält auf Eingabe![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* hält auf jeder Eingabe
=> f(w)=<M*>
=> M hält nicht auf Eingabe![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* hält auf keiner Eingabe
=> f(w)=<M*>![](/pool/data/tex/fb089645d59befb95237369363430bf1.gif)
![](/pool/data/tex/005e291af01e1f8456a32add6b9bc29b.gif)
![](/pool/data/tex/0433e3ca582ebe8bdc4f7186e8a6a925.gif)
![](/pool/data/tex/122b424e984e3cc587dd2f74a91fcb8c.gif)
![](/pool/data/tex/89bdabd6386a8c3132b4e3331c20d9fb.gif)
Konstruiere eine berechenbare Funktion f, die alle Ja/Nein-Instanzen von
![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
![](/pool/data/tex/361c74716a074bcec144a5b2332ce324.gif)
w Eingabe für
![](/pool/data/tex/334ad7613bd1623d7fc64c7002dbcd83.gif)
1.) Wenn w keine gültige GN, dann f(w)=w
2.) Wenn w=<M> GN einer TM, dann sei f(w) GN einer TM M* mit folgender Eigenschaft: M* ignoriert die Eingabe und simuliert M auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
f ist offensichtlich berechenbar. Falls w keine GN ist, so gilt
![](/pool/data/tex/59e01cdab501e9b98c28013b91095210.gif)
![](/pool/data/tex/8d0d7a1744a558dbf58bf0ba1bf34966.gif)
Für w=<M> ist f(w)=<M*>:
![](/pool/data/tex/d828fde91ed58532ec5452bad83f65c4.gif)
=> M hält auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* hält auf jeder Eingabe
=> f(w)=<M*>
![](/pool/data/tex/1484ef5f9664a5a5d293ed748686029d.gif)
![](/pool/data/tex/59e01cdab501e9b98c28013b91095210.gif)
=> M hält nicht auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=> M* hält auf keiner Eingabe
=> f(w)=<M*>
![](/pool/data/tex/fb089645d59befb95237369363430bf1.gif)