Vorlesung 6 Freudenberg

Aus ProgrammingWiki

- Effektiv berechenbar = eine Funktion die grundsätzlich gelöst werden kann
- S.6 „nicht definiert“ = eine Prozedur/ ein Verfahren, was niemals ein Ergebnis liefert
- S. 7 Totale Funktion: für jedes Argument gibt es einen Funktionswert
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)
- die Bestimmung des Funktionsbereiches ist algorithmisch nicht lösbar -> Beispiel für eine nicht berechenbare Funktion
- S. 9 „nfa“ -> nicht für alle

Übung S.11

- gilt nur für die natürlichen Zahlen, die Vorgängerfunktion für „0“ ist nicht definiert
- If n < 0 return 0
Else return n-1

- S.13 an den Stellen, wo die Funktion nicht definiert ist wird „a“ zurückgegeben
- S.15: Was liefert healt?(healt?)? der Selbstaufruf ist nicht berechenbar, da wir an dieser Stelle eine Fehler bekommen würden -> Antwort: Syntaxerror
- „healt?“ erwartet als Argument eine einstellige Funktion und eine natürliche Zahl (kann auch 0 sein)
- Healt? bekommt mit healt? aber eine Funktion die wieder eine Funktion erwartet
- S.18 A+ (ist die Menge A* ohne das leere Wort)
- Frage: Finden Sie einen Algorithmus, der die Indexliste sucht!

S. 30 Definieren Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.

Turing-entscheidbar:
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.

Turing-aufzählbar: (bei rekursiv aufzählbaren Sprachen L kann man eine TM konstruieren, die alle Elemente von L der Reihe nach „aufzählt“)
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.