Brainstorming VL07 Luepke
Aus ProgrammingWiki
< BuK | IIm19 | Ausarbeitungen Lüpke
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:
