Existe-t-il une courte construction explicite d'une fonction récursive universelle ? Toutes les définitions que j'ai vues impliquent la numérotation des machines Turing d'une manière ou d'une autre, ce qui est possible mais semble difficile et ingérable à écrire dans un langage de programmation de niveau supérieur (comme Python, Haskell, etc.)
9
Réponses:
Que diriez-vous de l'interprète Lisp original de McCarthy (à l'origine ici )? Il est universel, fonctionne sur un encodage naturel (un AST Lisp), ne s'appuie pas sur un interpréteur externe et fait environ 20 lignes.
la source
Sûr. Écrivez des routines qui calculent chacune des fonctions récursives primitives de Godel et écrivez une routine pour un opérateur de recherche illimité. L'ensemble des fonctions que vous pouvez calculer de cette manière est équivalent à l'ensemble des fonctions que les machines de Turing peuvent calculer. Plus d'informations ici .
L'inconvénient est que toute contribution à votre programme universel devrait être encadrée en termes de ces opérations simples. Bien sûr, c'est à cela que servent les compilateurs.
la source
Tout interprète pour n'importe quelle langue complète de Turing est une fonction récursive universelle. Il existe des interpréteurs pour les langages de haut niveau comme C ++ ou Python.
la source
Une fonction universelle
upeut être écrite assez facilement dans un langage de type Haskell (pas d'effets secondaires, fonctions d'ordre supérieur), à savoir:La fonction
uest universelle parce qu'elle accepte (la description) d' un programmefet d' une bande d'entréex, et vous indique le résultat de l' exécutionfsurx.Bien que cette réponse ne soit pas entièrement sérieuse, elle montre qu'un compilateur ou un interpréteur pour un langage de type Haskell contient déjà toutes les parties de construction nécessaires à une fonction universelle. La morale de l'histoire est qu'il vaut mieux passer du temps à étudier le fonctionnement des compilateurs et des interprètes que de s'inquiéter de la mise en œuvre d'une fonction universelle en termes de machines de Turing.
la source
uprend une fonction - je l'appellerais une fonction d'ordre supérieur. Je voudraisuprendre un entier ou un type de données algébrique régulier. Je ne force aucun modèle de calcul spécifique, tant que l'argument touest tangible - par exemple, il peut être sérialisé depuis / vers une chaîne.uprend une fermeture, qui est une séquence finie d'octets. Même dans le théorème utm habituel, l'entier quiuprend représente une fonction.Consultez également cet article de John Tromp, utilisant la logique combinatoire. Une version antérieure, apparemment plus disponible, était encore plus nette.
la source