Errata

Errata zum Skriptum Berechenbarkeit

Manche Bagatellen (Kommas, Trennungen, ganz evidente Tippfehler) werden hier nicht gelistet. Es werden aber alle mir zugetragenen Vorschläge in der folgenden Auflage verarbeitet. Allen, die mich auf weitere Fehler aufmerksam machen, danke ich im voraus.

Ein nachdrückliches Dankeschön an Herrn Wagenbrenner, der mir eine ausführliche Liste von Korrekturen zukommen ließ.

Seite 4: In Lemma 3.2 müsste die Funktion Pr heißen, nicht P.

Seite 6: In der vorletzten Zeile müsste es "uns" heißen.

Seite 8: Im Absatz vor Satz 4.3 fehlt im Wort "gesetzt" ein "e".

Seite 9: Im Beweis zu Satz 5.1 fehlt vor "übersetzen" ein Leerzeichen.

Seite 10, Mitte: "...$m$-stellige partielle Funktionen und $g$ eine $k$-stellige...", also das Wort "eine" ergänzen.

Seite 13: Über der Definition, im Teil (e) muss das Wort "ist" gestrichen werden.

Seite 14: Im Satz 6.1 ist für "R" bzw. "PR" die falsche Schrift gewählt worden.

Seite 15: Im Induktionsschluß von $y$ auf $y+1$ fehlt in der ersten Zeile eine schließende Klammer links von =.

Seite 16: Letzte Formel auf der Seite: es fehlt eine schließende Klammer.

Seite 25: Beweis von (*), erste Formelzeile: $h$ hat auch noch $y$ als Argument.

Seite 28, 5. Zeile: ergänze $(x)$ nach $\chi_{prim}$.

Seite 26: Im Programm A kann man statt l:=l-- auch einfach l-- schreiben.

Seite 33: In der Definition, (1), natürlich "und" statt "and".

Seite 34: Im zweiten Absatz fehlt ein Leerzeichen zwischen "Außenmaß" und "zu". Im dritten Absatz müßte es heißen "jetzt ist Pr die Vorgängerfunktion". Kurz danach: "pot" im falschen Schrifttyp.

Seite 35, Mitte: In der zweiten Formelzeile ist der Exponent an $e_k(m)$ nicht $m$, sondern $m+1$. Auch im Beweis von (*) ist viermal $m$ durch $m+1$ zu ersetzen (dreimal in der ersten Zeile, einmal nach "wegen" in der zweiten Zeile). Das Argument geht aber durch.

Seite 40: Im Beweis von 11.7 ergänze man nach der Def. von f die Worte: wie im Beweis von 11.5 (c).

Seite 46: Im ersten Absatz fehlt im Wort "können" ein "n" am Ende.

Seite 48: Die Programmierung der Shiftmaschine ist nicht ganz komplett, es fehlt das Löschen des zu transportierenden Strichs vor der Reise des Kopfes nach rechts und dem Neuschreiben. Details in der nächsten Auflage.

Seite 50:

Ein wesentlicher Fehler! Um den Ringbeweis zu beenden, muss gezeigt werden: Jede TM kann durch ein WHILE(nicht GOTO)-Programm simuliert werden.

Satz 14.4 muss entsprechend modifiziert werden; dies macht im Beweis keine ernsten Probleme. Details in der nächsten Auflage.

Seite 54, erste Zeile: next(v,y) anstelle von next(v,u).

Seite 55, unten: "för" muss offenbar "für" heißen.

Seite 56, letzte Formel im Beweis von 16.1: besser alle x durch x' ersetzen.

Seite 57, zweite Zeile von Bemerkung 2: \Phi(x,x) anstelle \Phi(x,2^x).

Seite 59, Anfang des Beweises von 17.3: streiche "Rüchführung... ...unentscheidbar ist", lies stattdessen: "Rüchführung eines Problems, das wir bereits als unentscheidbar erkannt haben, auf das neue Problem."

Seite 66, Proposition 19.3: Bezeichnung der Turingmaschine in der Formelzeile soll * (nicht +) sein.

Seite 67, zweiter Absatz von unten: Produkt läuft über alle $i$ mit $e_{i}=1$.

Seite 82: Die fehlende Skizze wird bei Gelegenheit nachgeliefert.

Seite 85: "raffiniert" im ersten Absatz ist vertippt.