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.

Quelle: Dr. Eva Richter u. Holger Arnold. Theoretische Informatik II Übungsblatt 2. Universität Potsdam. 2008. [https://www.cs.uni-potsdam.de/ti/lehre/08-Theorie-II/pdf/uebung-02.pdf Link] (13.05.2020).

== Entscheidbarkeit der Sprache P ==
Skizzen:

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

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