IIm18-Kreativaufgabe9

Aus ProgrammingWiki
< BuK < IIm18
Archivierte Version vom 2019-06-16T16:48:15+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


Implementierung der Kreativaufgabe (Java)

  • Das folgende Programm implementiert die Funktion k. Mit dieser kann das Wort aus dem Alphabet S* für die n-te Gödelnummer (unterliegt Gödelordnung) berechnet werden