Brainstorming VL07 Luepke
Aus ProgrammingWiki
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.
Quelle: Dr. Eva Richter u. Holger Arnold. Theoretische Informatik II Übungsblatt 2. Universität Potsdam. 2008. Link (13.05.2020).
Entscheidbarkeit der Sprache P
Skizzen:
