Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
57
Beweis:
ist nicht rekursiv aufzählbar
![](/pool/data/tex/361c74716a074bcec144a5b2332ce324.gif)
![](/pool/data/tex/c7a945044f1c34ba619f7f3a677f8ddd.gif)
w Eingabe für
![](/pool/data/tex/4a53bd52e0a7ead577de5ce5e13d1f71.gif)
1.) Wenn w keine gültige GN ist, liegt w in
![](/pool/data/tex/0433e3ca582ebe8bdc4f7186e8a6a925.gif)
![](/pool/data/tex/1484ef5f9664a5a5d293ed748686029d.gif)
2.) Wenn w=<M>, so ist f(w)=<M'>. M' verhält sich auf Eingabe x wie folgt:
Falls |x|=i, simuliert M' die ersten i Schritte von M auf
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
![](/pool/data/tex/0433e3ca582ebe8bdc4f7186e8a6a925.gif)
f ist offensichtlich berechenbar.Falls w=<M> gilt:
![](/pool/data/tex/04283e113ea841f20c919fb328305d85.gif)
=> M hält nicht auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=>
![](/pool/data/tex/ce63ea2c7462bda2d44e505c77f6ebf6.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=>
![](/pool/data/tex/f20daf383541d27af9906a2160f757ff.gif)
=> f(w)=<M'>
![](/pool/data/tex/1484ef5f9664a5a5d293ed748686029d.gif)
![](/pool/data/tex/321b3029af48fc526efcf50eb591266e.gif)
=> M hält auf Eingabe
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=>
![](/pool/data/tex/1d98d5ab33d4e5b332fba49d7976a055.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
=>
![](/pool/data/tex/1d98d5ab33d4e5b332fba49d7976a055.gif)
=> f(w)=<M'>
![](/pool/data/tex/fb089645d59befb95237369363430bf1.gif)