Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
45
Beweis: Wenn Sprachen
und
rekursiv (aufzählbar), dann auch
rekursiv (aufzählbar)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
![](/pool/data/tex/ae4cf62b01e4b538cc00de2654678903.gif)
![](/pool/data/tex/f0bfe2140faacda364f8c59f20b8ce82.gif)
![](/pool/data/tex/2c6f3b6c16df97a1b00e04ff17e4906e.gif)
![](/pool/data/tex/07cbd6c155424e110559a84df364be5a.gif)
Konstruieren eine TM M, die
![](/pool/data/tex/ae4cf62b01e4b538cc00de2654678903.gif)
- simuliere das Verhalten von
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
- Falls
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
=> M akzeptiert offensichtlich die Eingaben von
![](/pool/data/tex/ae4cf62b01e4b538cc00de2654678903.gif)
![](/pool/data/tex/0a04315fff14859d66e75bebbaaa6990.gif)
![](/pool/data/tex/2ce2507b1ae2246c8fd6f465f7bd2a28.gif)
![](/pool/data/tex/ae4cf62b01e4b538cc00de2654678903.gif)