Quelle est la différence entre les fonctions récursives primitives et les fonctions récursives générales ?

Les fonctions récursives primitives sont construites à l'aide de boucles bornées et se terminent toujours, mais elles ne capturent pas toutes les fonctions calculables. L'ajout de la minimisation non bornée, une recherche qui peut s'exécuter indéfiniment, produit les fonctions récursives générales, qui coïncident exactement avec les fonctions calculables par une machine de Turing.

Comment une machine avec seulement deux compteurs peut-elle être aussi puissante qu'un ordinateur ?

Minsky a montré que deux registres contenant des nombres naturels, avec seulement l'incrémentation, la décrémentation et le test de zéro, peuvent simuler une machine de Turing en encodant sa bande dans les registres. La construction est très inefficace, mais elle prouve qu'un matériel minimal atteint déjà la pleine puissance de calcul.

Fonctions récursives et machines à registres

La théorie des fonctions récursives construit les fonctions calculables à partir d'un petit nombre d'opérations de base, tandis que les machines à registres effectuent des calculs avec des nombres entiers stockés dans des registres. Ces deux modèles encadrent la machine de Turing et confirment la robustesse de la calculabilité.

Trouver un sujet avec PaperMindBientôtFind papers & topics

Tools & resources

Télécharger les diapositives

Learn & explore

VidéoBientôt

Definition

Les fonctions récursives générales sont celles construites à partir de constantes, de la fonction successeur et de projections par composition, récursion primitive et minimisation non bornée ; les machines à registres sont des dispositifs abstraits qui calculent en incrémentant, décrémentant et testant le contenu d'un ensemble fini de registres contenant des nombres naturels.

Scope

Ce sujet aborde les fonctions récursives primitives, l'ajout de la minimisation non bornée pour obtenir les fonctions récursives générales, la fonction d'Ackermann en tant que fonction calculable non primitivement récursive, les machines à registres et à compteurs et leur universalité, ainsi que l'équivalence de tous ces modèles avec la calculabilité de Turing.

Core questions

Comment les fonctions calculables peuvent-elles être définies arithmétiquement sans aucune machine ?
Pourquoi la minimisation non bornée est-elle nécessaire au-delà de la récursion primitive ?
Comment de simples machines à registres atteignent-elles la pleine puissance de calcul ?
Pourquoi ces modèles arithmétiques et de machines coïncident-ils avec les machines de Turing ?

Key theories

Équivalence avec la calculabilité de Turing: Les fonctions récursives générales et les fonctions calculées par les machines à registres sont exactement les fonctions calculables par une machine de Turing, ce qui renforce la thèse de Church-Turing à travers des modèles définis en termes purement arithmétiques et de machines élémentaires.
Au-delà de la récursion primitive: La fonction d'Ackermann est totale et calculable, mais sa croissance est trop rapide pour être primitivement récursive, ce qui démontre que la recherche non bornée est essentielle et que les fonctions récursives primitives constituent une sous-classe propre des fonctions calculables.
Universalité des machines à registres: Minsky a montré qu'une machine avec seulement deux compteurs et les opérations d'incrémentation, de décrémentation et de test de zéro est déjà Turing-complète, une démonstration extrême du peu de structure que nécessite un calcul complet.

Clinical relevance

Les machines à registres modélisent l'arithmétique entière des processeurs réels plus directement que ne le font les bandes ; la récursion primitive correspond à des programmes qui se terminent toujours et sous-tend les langages fonctionnels totaux et l'analyse de terminaison ; et la perspective des fonctions récursives relie le calcul aux fondements des mathématiques.

History

Gödel et Herbrand ont défini les fonctions récursives générales au début des années 1930, et Kleene a développé la théorie, y compris le rôle de la minimisation. Ackermann avait auparavant présenté sa fonction à croissance rapide, et Minsky a introduit les machines à registres et à compteurs dans les années 1960, prouvant l'universalité même des machines à deux compteurs.

Key figures

Kurt Gödel
Stephen Kleene
Wilhelm Ackermann
Marvin Minsky

Seminal works

cutland1980
minsky1967

Frequently asked questions

Quelle est la différence entre les fonctions récursives primitives et les fonctions récursives générales ?: Les fonctions récursives primitives sont construites à l'aide de boucles bornées et se terminent toujours, mais elles ne capturent pas toutes les fonctions calculables. L'ajout de la minimisation non bornée, une recherche qui peut s'exécuter indéfiniment, produit les fonctions récursives générales, qui coïncident exactement avec les fonctions calculables par une machine de Turing.
Comment une machine avec seulement deux compteurs peut-elle être aussi puissante qu'un ordinateur ?: Minsky a montré que deux registres contenant des nombres naturels, avec seulement l'incrémentation, la décrémentation et le test de zéro, peuvent simuler une machine de Turing en encodant sa bande dans les registres. La construction est très inefficace, mais elle prouve qu'un matériel minimal atteint déjà la pleine puissance de calcul.