Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
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.