Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
12
Wann heißt eine Funktion TM-berechenbar?
Eine TM M, die für alle Eingaben terminiert, berechnet eine totale Funktion 
.
Da TMs im Allgemeinen nicht immer terminieren berechnen sie also eine Funktion
Eine Eingabe
wird auf 
abgebildet, wenn M auf der Eingabe x nicht terminiert. Sonst steht der Kopf im Stoppzustand auf einem Zeichen aus 
. Wenn das Ergebnis 
ist steht der Kopf auf B.
Eine Funktion
heißt TM-berechenbar, wenn es eine TM M mit 
gibt.
.Da TMs im Allgemeinen nicht immer terminieren berechnen sie also eine Funktion
Eine Eingabe
wird auf abgebildet, wenn M auf der Eingabe x nicht terminiert. Sonst steht der Kopf im Stoppzustand auf einem Zeichen aus . Wenn das Ergebnis ist steht der Kopf auf B.Eine Funktion
heißt TM-berechenbar, wenn es eine TM M mit gibt. 