This flashcard is just one of a free flashcard set. See all flashcards!
52
Lemma Reduktion
Falls 
und 
rekursiv (rekursiv aufzählbar) ist, so ist auch 
rekursiv (rekursiv aufzählbar).
Beweis:
akz. 
akz. 
Falls rekursiv ist, ist die Terminierung von auf jeder Eingabe gesichert. Falls rek. aufz. ist, ist die Terminierung von auf Eingaben aus gesichert.
und rekursiv (rekursiv aufzählbar) ist, so ist auch rekursiv (rekursiv aufzählbar).Beweis:
akz. akz. Falls
rekursiv ist, ist die Terminierung von auf jeder Eingabe gesichert. Falls rek. aufz. ist, ist die Terminierung von auf Eingaben aus gesichert.