IIm18-Kreativaufgabe9

Aus ProgrammingWiki
< BuK < IIm18
Archivierte Version vom 2019-06-16T16:37:03+00:00. Aktuelle Version

Kernaussagen der Vorlesung

  • nicht alle total berechenbare Funktionen sind primitv-rekursiv (AP-Funktion)
  • man kann keine nicht totale Funktion als primitiv-rekursive Funktion darstellen
  • man kann mit dem μ-Operator μ-rekursive (d.h. partiell-rekursive) Funktionen darstellen. Diese sind so aufgebaut, dass man weiß wie oft eine Funktion höchstens durchlaufen wird (obere Schranke) -> damit lassen sich nun auch * nicht totale Funktion sowie alle primitiv-rekursive Funktionen darstellen
  • Die Menge der Turing-berechenbaren Funktionen und die Menge der μ-rekursiven Funktionen (partiell berechenbare Funktionen) sind identisch.
  • μ-rekursive Funktionen können mit while-Programmen implementiert werden