µ-Rekursion
Von: , Frage gestellt am Fr, 22. Jun 2001
Hallo,
wer kann mir in einfachen Wort erklären, wozu genau die µ-Rekursion da ist? Die Erklärung in unserem Script kann ich nicht ganz nachvollziehen.
Danke,
Golo Haas
1 Antworten zu dieser Frage
-
Antwort von nach 4 Tagen 1 hilfreich
Re: µ-Rekursion
Der my-Operator erlaubt im Gegensatz zum beschränkten Suchoperator ein Suchen das evtl. nicht abbricht (in Pascal
while statt for). Der Punkt ist der: Wenns immer abbricht kann
man ueber die entstehenden Programmklassen diagonalisieren und bekommt eine berechenbare Funktion, die aber nicht in der betrachteten Klasse drin ist. Da man aber die Klasse aller
intuitiv berechenbaren Funktionen sucht, will man das halt nicht.
Fuer die my-Rekusriven Funktionen kann man dann zeigen, dass sie
mit der Klasse der turingmerechenbaren Funktionen uebereinstimmt.
S, z.B. das Buch von Blum ISBN 3-486-24279-2 [Buch anschauen]
MfG
Martin [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]