This flashcard is just one of a free flashcard set. See all flashcards!
14
TM-entscheidbar für Entscheidungsprobleme (Sprachen)
Eine Sprache 
heißt TM-entscheibar bzw. rekursiv, wenn es eine TM gibt, die auf allen Eingaben stoppt und die Eingabe aktzeptiert, wenn 
, und die Eingabe verwirft, wenn 
.
heißt TM-entscheibar bzw. rekursiv, wenn es eine TM gibt, die auf allen Eingaben stoppt und die Eingabe aktzeptiert, wenn , und die Eingabe verwirft, wenn .