µ-rekursive Funktionen

Wissenschaft Physik
1

Hallo,

kann jemand mit einfachen Worten erklären, was µ-rekursive Funktionen sind ? Das ist echt schwierig zu verstehen.

Danke und Grüße,

Tris

2

Hallo,

kann jemand mit einfachen Worten erklären, was µ-rekursive
Funktionen sind ? Das ist echt schwierig zu verstehen.

kannst Du mit dem eingeschränkten Begriff der „primitiven Rekursion“ etwas anfangen ? Die Analogie wäre dann

primitive Rekursion:

  • ausschließlich terminierende Schleifen
  • totale Funktionen
  • echte Teilemenge der rekursiven Sprachen (Beweis: Ackermannfunktion)

µ-Rekursion:

  • beliebige Schleifen (deren Terminierung nicht gesichert und allgemein auch nicht überprüfbar ist, s.h.Halteproblem)
  • evtl. partielle Funktionen
  • Turing mächtig resp. Chomsky 0

Gruss
Enno