This flashcard is just one of a free flashcard set. See all flashcards!
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![](/pool/data/tex/ce8e7ba4bfa2eba6ec782d7b76c26145.gif)
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.
![](/pool/data/tex/735082882f3a4914de56ea98144794fe.gif)
Da TMs im Allgemeinen nicht immer terminieren berechnen sie also eine Funktion
![](/pool/data/tex/ce8e7ba4bfa2eba6ec782d7b76c26145.gif)
Eine Eingabe
![](/pool/data/tex/0c45e03bcc795af48f72c87b6a40ee3b.gif)
![](/pool/data/tex/b70979a357cfbe7c61e4c686ea2beb93.gif)
![](/pool/data/tex/07710b5c43702a8bb7b9104eacc6ba71.gif)
![](/pool/data/tex/92e4da341fe8f4cd46192f21b6ff3aa7.gif)
Eine Funktion
![](/pool/data/tex/eb8cac6adb2a63c39d9378a0e1808fd4.gif)
![](/pool/data/tex/dce20eab99b6cea2bef9695b84f2fb2b.gif)