This flashcard is just one of a free flashcard set. See all flashcards!
45
Beweis: Wenn Sprachen 
und 
rekursiv (aufzählbar), dann auch 
rekursiv (aufzählbar)
und rekursiv (aufzählbar), dann auch rekursiv (aufzählbar)
zwei TMn, die bzw. entscheiden (erkennen).Konstruieren eine TM M, die
entscheidet (erkennt)- simuliere das Verhalten von
auf w, dann das Verhalten von 
auf w- Falls
und akzeptieren, so auch M=> M akzeptiert offensichtlich die Eingaben von
, da sowohl als auch auf jeder Eingabe halten. Also entscheidet (erkennt) M die Sprache .