Gibt es eine kurze explizite Konstruktion einer universellen rekursiven Funktion ? Alle Definitionen, die ich gesehen habe, beinhalten die Nummerierung von Turing-Maschinen in irgendeiner Weise, was möglich ist, aber schwierig und unüberschaubar erscheint, in einer höheren Programmiersprache (wie Python, Haskell usw.) zu schreiben.
9
Antworten:
Wie wäre es mit McCarthys ursprünglichem Lisp-Interpreter (ursprünglich hier )? Es ist universell, arbeitet mit einer natürlichen Codierung (einem Lisp AST), ist nicht auf einen externen Interpreter angewiesen und umfasst etwa 20 Zeilen.
quelle
Sicher. Schreiben Sie Routinen, die jede der primitiven rekursiven Funktionen von Godel berechnen , und schreiben Sie eine Routine für einen unbegrenzten Suchoperator. Der Funktionsumfang, den Sie auf diese Weise berechnen können, entspricht dem Funktionsumfang, den Turing-Maschinen berechnen können. Weitere Informationen hier .
Der Nachteil ist, dass jede Eingabe in Ihr universelles Programm in Bezug auf diese einfachen Operationen gerahmt werden muss. Dafür sind Compiler natürlich da.
quelle
Jeder Interpreter für jede Sprache, die vollständig ist, ist eine universelle rekursive Funktion. Es gibt Interpreter für Hochsprachen wie C ++ oder Python.
quelle
Eine universelle Funktion
ukann recht einfach in einer Haskell-ähnlichen Sprache geschrieben werden (keine Nebenwirkungen, Funktionen höherer Ordnung), nämlich:Die Funktion
uist universell , weil sie akzeptiert (die Beschreibung) , ein Programmfund einen Eingabebandx, und sagt Ihnen , das Ergebnis der Ausführungfaufx.Diese Antwort ist zwar nicht ganz ernst, zeigt jedoch, dass ein Compiler oder ein Interpreter für eine Haskell-ähnliche Sprache bereits alle für eine universelle Funktion erforderlichen Bauteile enthält. Die Moral der Geschichte ist, dass Zeit besser damit verbracht wird, die Funktionsweise von Compilern und Interpreten zu untersuchen, als sich Gedanken über die Implementierung einer universellen Funktion in Bezug auf Turing-Maschinen zu machen.
quelle
unimmt eine Funktion - ich habe es eine Funktion höherer Ordnung nennen würde. Ich möchteueine Ganzzahl oder einen regulären algebraischen Datentyp verwenden. Ich erzwinge kein bestimmtes Berechnungsmodell, solange das Argument dazuugreifbar ist - zum Beispiel kann es von / zu einer Zeichenfolge serialisiert werden.uwird ein Abschluss vorgenommen, bei dem es sich um eine endliche Folge von Bytes handelt. Selbst im üblichen utm-Theoremurepräsentiert die ganze Zahl, die nimmt, eine Funktion.Überprüfen Sie auch dieses Papier von John Tromp mit kombinatorischer Logik. Ein früherer Bericht, der anscheinend nicht mehr verfügbar war, war noch ordentlicher.
quelle