Primitive Recursive Functions pour les programmeurs en pratique

Fonctions récursives primitives : guide pour les programmeurs en pratique

Les programmeurs utilisent souvent le terme « complétude de Turing ». Dans certains domaines, le fait de ne pas être Turing-complet est même considéré comme une qualité ou une exigence. Cependant, la plupart des discussions reposent sur des idées erronées. Ce que signifie réellement le fait de ne pas être Turing-complet est différent. La complétude de Turing est un terme mathématique au sens très précis. Il n’est pas permis de le réinterpréter pour d’autres usages.

Partie I : résumé

• Si un programme écrit dans un langage Turing-complet s’exécute plus vite que O(22N), alors il peut aussi être implémenté dans un langage non Turing-complet.
• La plupart des problèmes pratiques sont plus rapides que « deux puissance deux puissance deux ».
• Un langage non Turing-complet n’impose pas de limitation pratique.
• Un programme qui ne se termine pas, ou qui met un temps énorme à se terminer, doit être traité de la même manière.

Partie II : fonctionnement des machines

Machines à états finis (Finite State Machines)

• Une machine à états finis prend une chaîne en entrée et renvoie « oui » ou « non ».
• Elle possède un nombre fini d’états.
• La fonction de transition d’état prend l’état courant et le symbole d’entrée suivant, puis renvoie un nouvel état.
• Une machine à états finis ne peut pas entrer dans une boucle infinie.
• Une machine à états finis a la même expressivité que les expressions régulières.

Machines de Turing (Turing Machines)

• Une machine de Turing est un peu plus complexe qu’une machine à états finis.
• Une machine de Turing fonctionne à l’aide d’un ruban de taille variable.
• La fonction de transition d’état prend l’état courant et le symbole courant du ruban, puis renvoie un nouvel état, un symbole et une direction de déplacement.
• Une machine de Turing fonctionne comme une fonction et peut entrer dans une boucle infinie.
• Une machine de Turing peut simuler une machine à états finis.

Programmer des machines de Turing

• Une machine de Turing possède un ruban infini.
• Une machine de Turing n’exécute pas un programme fourni par l’utilisateur. Le programme est codé en dur dans la machine.
• Une machine de Turing universelle peut simuler d’autres machines de Turing.
• Une machine de Turing a la même capacité de calcul que des langages comme Python.

Limites des machines de Turing

• Il existe des fonctions qu’on ne peut pas implémenter avec une machine de Turing.
• On peut énumérer toutes les machines de Turing, mais pas toutes les fonctions.
• Certains problèmes (par ex. le problème de l’arrêt) ne peuvent pas être résolus par une machine de Turing.
• La puissance des machines de Turing rend impossible de déterminer si un programme se terminera.

Partie III : retour aux problèmes pratiques

Fonctions récursives primitives (Primitive Recursive Functions)

• Les fonctions récursives primitives sont des fonctions qui prennent en entrée un tuple de nombres naturels et renvoient un nombre naturel.
• Elles partent des fonctions zero et succ pour construire d’autres fonctions.
• La récursion générale n’est pas autorisée, mais une forme limitée de boucle l’est.
• On peut définir des opérations comme l’addition, la multiplication et l’exponentiation.
• On peut définir des opérateurs logiques et des conditions.
• Les nombres sont utilisés pour représenter des structures de données.

Le point à retenir de GN⁺

• Cet article a été écrit pour aider à comprendre la complétude de Turing et les fonctions récursives primitives.
• Il explique ce que signifie concrètement, dans la pratique, le fait de ne pas être Turing-complet.
• Il présente les différences entre les machines à états finis et les machines de Turing, et discute des limites de ces dernières.
• Il explique la définition et l’utilisation des fonctions récursives primitives.
• Cet article aidera les programmeurs à mieux comprendre la complétude de Turing et les fonctions récursives primitives.
• Parmi les projets aux fonctionnalités similaires, on trouve les « expressions régulières » et les « machines à états finis ».