Brainstorming VL07 Luepke
Aus ProgrammingWiki
Archivierte Version vom 2020-05-13T08:03:46+00:00. Aktuelle Version
Wiederholung zum intuitiven Berechenbarkeitsbegriff
Eine Funktion f: \Sigma^{∗} \rightarrow \Sigma^{∗} auf W Wörtern über dem Alphabet \Sigma heißt partiell berechenbar, wenn es eine Turingmaschine M_{f} gibt, die auf jeder Eingabe w aus dem Definitionsbereich von f mit dem Funktionswert f(w) auf dem Band anhält und auf jeder anderen Eingabe nicht anhält.
Die Funktion f heißt total berechenbar, wenn sie partiell berechenbar und auf jedem Wort aus \Sigma^{*} definiert ist.
Entscheidbarkeit der Sprache P
Skizzen:
