BuK/IIm19/Ausarbeitungen Lüpke/Brainstorming VL07 Luepke

Wiki-Quelltext dieser Seite.

== 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:

[[Bild:Flikkes_IMG_20200506_113612230-1-.jpg|300px]]

[[Bild:Flikkes_IMG_20200506_113634275-1-.jpg|200px|degree=180]]