Rekursionstheorie (Vorles. und Pruefungsstoff)

Grundlegendes

Haupt-Erkenntnis: Alle "vernuenftigen" Computermodelle sind aequivalent.

Ein Computer hat:

• endliches (aber beliebig langes) Programm=Source-Code
  Bemerkung: ein source code(=Zeichenkette bzw endliche Folge von Befehlen) entspricht auf kanonischer Wise einer natuerlichen Zahl (bei uns: der Goedel Nummer der Registermaschine)
• es steht potentiell unendlich viel Speicher und potentiell unendlich lange Zeit fuer eine Berechnung zur Verfuegung (aber eine konkrete, erfolgreiche Berechnung verwendet immer nur endlich viel Speicher und endet nach endlicher Zeit)

Haupt-Erkenntnis: Es gibt universelles Programm.
Im Computeralltag entspricht das einfach einem Interpreter (ein Programm, das beliebigen Sourcecode P und inputwert x als Input nimmt, und als output P(x) liefert).
In der Vorlesung: Folgt aus Kleene Praedikat, im wesentlichen: Die Eigenschaft "Das Programm m haelt auf Input x nach t schritten mit output y" ist entscheidbar (sogar: primitiv rekursiv). Siehe Seite 19 der Mitschrift.
Folgerungen:

• Unloesbarkeit des Halteproblems, (Beweis: Versuche einen Diagonalbeweis: Es gibt nur abzaehlbar viele berechenbare Funktionen, durch das universelel Programm kann man diese Funktionen sogar aufzaehlen, und effektiv dir funktion g(n)=f_n(n)+1 definieren. Das ist kein Widerspruch wenn die f_n nur partielle Funktionen sind. Waere das Halteproblem rekursiv loesbar, koennte man mit Fallunterscheifung aber sehr wohl einen widerspruechliche Diagonalfunktion g' definieren)
• Notwendigkeit partieller Funktionen (man kann "Endlosschleifen" oder dergl nicht durch kluge Konzeption einer Programmiersprache vermeiden; sonst waere das universelle Programm ein Widerspruch, siehe Mitschrift S20)

Entscheidbare und r.e. Mengen

Wir haben uns auch mit Teilmengen A von N beschaeftigt. Da gibt es zusaetzlich zu rekursiv (entscheidbar) auch den wichtigen Begriff rekursiv aufzaehlbar. Es gibt einige wichtige Eigenschaften (A ist rekursic gdw A und das Komplement von A r.e. etc etc)

Kodierungen, Anwendungen

Wir haben uns in der Untersuchung auf Funktionen von N nach N (etwas allgemeiner: von N^n nach N) beschraenkt. Wichtige Erkenntnis: aequivalenterweise kann man endliche Zeichenketten, beliebig lange endliche Tupel von natuerlichen Zahlen, rationale Zahlen etc verwenden (wobei man jeweil "vernuenftige" bijektionen auf N angeben kann).

Eine wichtige Anwendung von Kodierung ist die Goedel-nummerierung der Registermaschinen, die man zB fuer das universelle Programm braucht.

Wir haben erwaehnt (aber nicht bewisen) dass neben dem Halteproblem auch zwei wichtige Probleme in der Mathematik r.e. aber nicht entscheidbar sind: Das 10. Hilbertsche Problem und das Wortproblem in Gruppen.