IIm18-Kreativaufgabe9

Aus ProgrammingWiki
< BuK < IIm18
Archivierte Version vom 2019-06-16T16:44:33+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 unbeschränkten μ-Operator μ-rekursive (d.h. partiell-rekursive) Funktionen darstellen. Diese sind so aufgebaut, dass es zu einem Endloszyklus kommen kann, wenn die geforderte Bedingung niemals erfüllt werden kann
  • 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