BuK/IIm20/Vorlesung 6 Freudenberg

Wiki-Quelltext dieser Seite.

-	Effektiv berechenbar = eine Funktion die grundsätzlich gelöst werden kann <br\>
-	S.6 „nicht definiert“ = eine Prozedur/ ein Verfahren, was niemals ein Ergebnis liefert <br\>
-	S. 7	Totale Funktion: für jedes Argument gibt es einen Funktionswert <br\>
Partielle Funktion: es gibt Argumente aus dem Vorbereich, für die es keinen Funktionswert gibt, an diesen Stellen ist die Funktion nicht definiert (sie stoppt nicht) <br\>
-	die Bestimmung des Funktionsbereiches ist algorithmisch nicht lösbar -> Beispiel für eine nicht berechenbare Funktion <br\>
-	S. 9 „nfa“ -> nicht für alle <br\>

Übung S.11 <br\>

-	gilt nur für die natürlichen Zahlen, die Vorgängerfunktion für „0“ ist nicht definiert <br\>
-	If n < 0 return 0 <br\>
Else return n-1 <br\>
<br\>
-	S.13 an den Stellen, wo die Funktion nicht definiert ist wird „a“ zurückgegeben <br\>
-	S.15: Was liefert healt?(healt?)? der Selbstaufruf ist nicht berechenbar, da wir an dieser Stelle eine Fehler bekommen würden -> Antwort: Syntaxerror <br\>
-	„healt?“ erwartet als Argument eine einstellige Funktion und eine natürliche Zahl (kann auch 0 sein) <br\>
-	Healt? bekommt mit healt? aber eine Funktion die wieder eine Funktion erwartet <br\>
-	S.18 A+ (ist die Menge A* ohne das leere Wort) <br\>
-	Frage: Finden Sie einen Algorithmus, der die Indexliste sucht! <br\>
<br\>
'''S. 30 Definieren Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.''' <br\>
<br\>
'''Turing-entscheidbar:''' <br\>
Eine Sprache L ist entscheidbar (=berechenbar=rekursiv), wenn es eine TM ‚M‘ gibt, die ihr Wortproblem entscheidet, d.h. ‚M‘ ist Entscheidbar und L = L(M). Andernfalls heißt L unentscheidbar.
L ist semi-entscheidbar (=Turing-erkennbar=Turing-akzeptierbar=rekursiv aufzählbar) wenn es eine TM ‚M‘ gibt die L = L(M), auch wenn M kein Entscheider ist.<br\>
<br\>
'''Turing-aufzählbar:''' (bei rekursiv aufzählbaren Sprachen L kann man eine TM konstruieren, die alle Elemente von L der Reihe nach „aufzählt“) <br\>
Ein Aufzähler ist eine deterministische Turingmaschine M mit einem speziellen Zustand qAusgabe. Immer wenn M in den Zustand qAusgabe gelangt, wird der aktuelle Bandinhalt – vom Anfang bis zum ersten Zeichen, nach dem nur noch _(Leerzeichen) folgen – ausgegeben.
Die durch M aufgezählte Sprache ist die Menge aller Wörter aus ∑*, die M ausgibt, wenn M auf dem leeren Band gestartet wird.