Pourquoi les langages fonctionnels Turing sont-ils complets?

Peut-être que ma compréhension limitée du sujet est incorrecte, mais c'est ce que je comprends jusqu'à présent:

• La programmation fonctionnelle est basée sur Lambda Calculus, formulée par Alonzo Church.

• La programmation impérative est basée sur le modèle de machine Turing, fabriqué par Alan Turing, étudiant de Church.

• Le calcul lambda est aussi puissant et capable que la machine de Turing,
  ce qui signifie qu'ils sont équivalents en puissance de calcul.

Si la programmation fonctionnelle est basée sur Lambda Calculus et non sur la machine Turing, alors pourquoi certains (ou tous) d'entre eux sont décrits comme étant Turing complet, et non Lambda complet ou quelque chose comme ça? Le terme "complétude de Turing" est-il spécial de quelque façon que ce soit aux machines de Turing, ou est-ce juste un mot?

Enfin, si les langages impératifs sont basés sur la machine de Turing et que les ordinateurs sont essentiellement des machines de Turing, sans mémoire infinie, cela signifie-t-il qu'ils fonctionnent mieux que les langages de programmation fonctionnels sur nos PC modernes?

Si tel est le cas, quel serait l'équivalent d'une machine à calculer lambda?

Je sais que cela semble être 3 questions distinctes, mais elles sont toutes étroitement liées, et chacune dépend de la question précédente étant une question valide pour commencer.

En bref :

Ce qui caractérise les langages de programmation impératifs comme proches des machines Turing et des ordinateurs habituels tels que les PC (eux-mêmes plus proches des machines à accès aléatoire (RAM) plutôt que de la machine Turing) est le concept d'une mémoire explicite qui peut être modifiée pour stocker (résultats intermédiaires ). Il s'agit d'une vue automate du calcul, avec un concept d'état (comprenant à la fois le contrôle d'état fini et le contenu de la mémoire) qui peut changer au fur et à mesure du calcul.

La plupart des autres modèles sont plus abstraits. Bien qu'elles puissent exprimer le calcul comme une succession d'étapes de transformation d'une structure originale, ces transformations sont appliquées dans une sorte d'univers intemporel de significations mathématiques. Cela peut préserver des propriétés, telles que la transparence référentielle, qui peuvent simplifier l'analyse mathématique. Mais il est plus éloigné des modèles physiques naturels qui reposent sur le concpet de la mémoire.

Il n'y a donc pas de machines fonctionnelles naturelles, sauf dans un sens plus large comme expliqué ci-dessous, car le logiciel n'est pas vraiment séparable du matériel.

La référence à Turing comme référence de calculabilité vient probablement du fait que son modèle, la machine de Turing, était le plus proche de cette contrainte de réalisabilité physique, ce qui en faisait un modèle de calcul plus intuitif.

Autres considérations :

Il existe de nombreux modèles de calcul, qui ont été conçus pour saisir de la manière la plus générale possible le concept de calcul. Ils incluent les machines de Turing, en fait dans de nombreuses saveurs différentes, le lambda calcul (les saveurs aussi), les systèmes de réécriture semi-Thue, la fonction récursive partielle, la logique combinatoire.

Ils capturent tous certains aspects des diverses techniques utilisées par les mathématiciens pour exprimer ou effectuer des calculs. Et la plupart ont été utilisés dans une certaine mesure comme base de la conception de certains langages de programmation (par exemple Snobol pour les systèmes de réécriture, APL pour les combinateurs, Lisp / Scheme pour le calcul lambda) et peuvent souvent être combinés de diverses manières dans les langages de programmation modernes.

Un résultat majeur est que tous ces modèles de calcul se sont révélés équivalents, ce qui conduit à la thèse de Church-Turing selon laquelle aucun modèle de calcul physiquement réalisable ne peut faire plus que n'importe lequel de ces modèles. Un modèle de calcul est dit Turing complet s'il peut être prouvé qu'il est équivalent à l'un de ces modèles, donc équivalent à tous.

Le nom aurait pu être différent. Le choix de la machine de Turing (TM) comme référence est probablement dû au fait qu'il s'agit probablement du plus simple de ces modèles, imitant étroitement (mais de manière simpliste) la façon dont un humain calcule et assez facile à mettre en œuvre (sous une forme finie limitée ) en tant qu'appareil physique, à tel point que les machines de Turing ont été construites avec des ensembles Lego . L'idée de base ne nécessite aucune sophistication mathématique. C'est probablement la simplicité et la réalisabilité du modèle qui lui ont donné cette position de référence.

Au moment où Alan Turing a créé son dispositif informatique, d'autres propositions étaient sur la table pour servir de définition formelle de la calculabilité, une question cruciale pour les fondements des mathématiques (voir Entscheidungsproblem ). La proposition de Turing a été considérée par les experts de l'époque comme celle qui englobe le plus de façon convaincante les travaux connus sur ce que devrait être la calculabilité (voir Calculabilité et récursivité , RI Soare, 1996, voir section 3.2). Les différentes propositions se sont avérées équivalentes, mais celles de Turing ont été plus convaincantes. _{[extrait des commentaires de Yuval Filmus]}

Il convient de noter que, d'un point de vue matériel, nos ordinateurs ne sont pas des machines Turing, mais plutôt ce qu'on appelle des machines à accès aléatoire (RAM) , qui sont également Turing complètes.

Le langage purement impératif (quoi que cela puisse signifier) ​​sont probablement les formalismes utilisés pour les modèles les plus élémentaires, tels que les machines de Turing, ou le langage d'assemblage (en sautant son codage binaire) des ordinateurs. Les deux sont notoirement illisibles et très difficiles à écrire avec des programmes importants. En fait, même le langage d'assemblage possède des fonctionnalités de niveau supérieur pour faciliter un peu la programmation, par rapport à l'utilisation directe des instructions machine. Les modèles impératifs de base sont fermés aux mondes physiques, mais peu utilisables.

Cela a rapidement conduit au développement de modèles de calcul de niveau supérieur, qui ont commencé à y mélanger une variété de techniques de calcul, telles que les sous-programmes et les appels de fonction, la dénomination de l'emplacement de la mémoire, la portée des noms, la quantification et les variables fictives, déjà utilisées sous une certaine forme en mathématiques et en logique, et même des concepts très abstraits tels que la réflexion ( Lisp 1958).

La classification des langages de programmation en paradigme de programmation tels qu'impératif, fonctionnel, logique, orienté objet est basée sur la prééminence de certaines de ces techniques dans la conception du langage, et la présence ou l'absence de certaines fonctionnalités informatiques qui imposent certaines propriétés pour les programmes ou des fragments de programme écrits dans la langue.

Certains modèles conviennent aux machines physiques. Certains autres sont plus pratiques pour une description de haut niveau des algorithmes, celle-ci pouvant dépendre du type d'algorithme à décrire. Certains théoriciens utilisent même des spécifications non déterministes d'algorithmes, et même que cn soit traduit en termes de programmation plus conventionnels. Mais il n'y a pas de problème de non-concordance, car nous avons développé une technologie sophistiquée de compilateur / interprète qui peut traduire chaque modèle en un autre selon les besoins (qui est également la base de la thèse de Church-Turing).

Maintenant, vous ne devez jamais considérer votre ordinateur comme du matériel brut. Il contient des circuits booléens qui effectuent un traitement très élémentaire. Mais une grande partie est dirigée par des micro-programmes à l'intérieur de l'ordinateur que vous ne connaissez jamais. Ensuite, vous avez le système d'exploitation qui fait que votre machine semble encore différente de ce que fait le matériel.En plus de cela, vous pouvez avoir une machine virtuelle qui exécute le code d'octet, puis un langage de haut niveau tel que Pyva et Jathon, ou Haskell , ou OCaml, qui peut être compilé en code octet.

À chaque niveau, vous voyez un modèle de calcul différent. Il est très difficile de séparer le niveau matériel du niveau logiciel et ainsi d'affecter un modèle de calcul spécifique à une machine. Et comme ils sont tous traduisibles, l'idée d'un modèle de calcul matériel ultime est à peu près une illusion.

La machine de calcul lambda existe: c'est un ordinateur qui peut réduire les expressions de calcul lambda. Annonce qui se fait facilement.

À propos des architectures de machines spécialisées

En fait, pour compléter la réponse de Peter Taylor et pour assurer le suivi des jumelages matériel / logiciel, des machines spécialisées ont été produites pour être mieux adaptées à un paradigme spécifique, et leurs logiciels de base ont été écrits dans un langage de programmation basé sur ce paradigme.

Ceux-ci inclus

• Le Burroughs B5000 et ses successeurs (années 60), qui ont été adaptés pour une mise en œuvre efficace de la récursivité, représentés à l'époque par le langage Algol 60 .

• Le Western Digital WD / 9000 Pascal MicroEngine , une machine basée sur un bytecode microprogrammé spécialisé pour le langage de programmation Pascal , au début des années 1980.

• Plusieurs marques de Lisp Machines dans les années 80.

Fondamentalement, ce sont également des structures matérielles impératives, mais atténuées par des fonctionnalités matérielles spéciales ou des interprètes microprogrammés pour mieux s'adapter au paradigme souhaité.

En fait, le matériel spécialisé pour des paradigmes spécifiques ne semble pas avoir réussi à long terme. La raison en est que la technologie de compilation pour implémenter n'importe quel paradigme sur le matériel vanilla est devenue de plus en plus efficace, de sorte que le matériel spécialisé n'était pas tellement nécessaire. De plus, les performances du matériel informatique s'amélioraient rapidement, mais le coût de l'amélioration (y compris l'évolution des logiciels de base) était plus facilement amorti sur du matériel vanille que sur du matériel spécialisé. Le matériel spécialisé ne pouvait pas rivaliser à long terme.

Néanmoins, et bien que je ne dispose pas de données précises à ce sujet, je soupçonne que ces entreprises ont laissé des idées qui ont influencé l'évolution des machines, des mémoires et de l'architecture des jeux d'instructions.

Turing-complete n'est qu'un nom. Vous pouvez l'appeler Abdul-complete si vous le souhaitez. Les noms sont décidés historiquement et sont souvent nommés d'après les «mauvaises» personnes. C'est un processus sociologique qui n'a pas de critères clairs. Le nom n'a pas de sens au-delà de sa sémantique officielle.

Les langages impératifs ne sont pas basés sur les machines Turing. Ils sont basés sur des machines RAM. Votre ordinateur est une machine RAM. Les machines de Turing sont un joli modèle théorique, mais elles ne sont pas un très bon modèle d'ordinateurs réels.

Les langages de programmation basés sur d'autres paradigmes peuvent être très efficaces, même si le processeur sous-jacent ne les prend pas en charge de manière native; par exemple, les imprimantes exécutent un langage de pile. La programmation ne se limite pas au code machine.

Parce que "Turing-complete" signifie simplement "il peut calculer tout ce qu'une machine Turing peut calculer."

Une de vos questions ne semble pas avoir encore reçu de réponse:

Si tel est le cas, quel serait l'équivalent d'une machine à calculer lambda?

UNE machine Lisp . Matériel conçu spécifiquement pour s'adapter au modèle de calcul LISP. L'article de Wikipédia parle de produits commerciaux, mais mon directeur des études à l'université en avait un fabriqué à la main dans son bureau.

Les langages fonctionnels sous forme de calcul lambda inventé par Church se sont avérés complets. c'est une preuve mathématique réelle qui peut être trouvée dans les articles scientifiques publiés en "réduisant" le calcul lambda aux opérations / calculs sur les machines de Turing. à l'époque de l'article de Turings de 1936 et après, différents modèles de calcul «complets» ont été proposés / en circulation. c'était pas immédiatement réalisé que tous étaient équivalents. la ou les preuves de leur équivalence ont été publiées à la fin des années 30 et 40 après le papier Turings.

la machine de Turing est conceptuellement (mais pas fonctionnellement) plus simple que les autres modèles et c'est probablement une partie importante de la raison pour laquelle l'intégralité de Turing porte son nom. d'autres idées telles que le lambda calcul sont plus abstraites et ont commencé / sont principalement issues de la théorie mathématique / logique. Turing a proposé une machine . une "machine" est littéralement un "appareil physique" théorique . c'est un objet / construction conceptuel remarquable qui relie / unifie deux mondes différents, appliqué et théorique. il donne un nouveau sens abstrait aux entités physiques, par exemple "le temps et l'espace". ce n'est pas une simple coïncidence si les mathématiciens se réfèrent parfois à la "technologie", aux "machines" ou aux "appareils" de preuves. Turing a réussi à fusionner ingénieusement tout cela dans son invention conceptuelle. sa définition est assez simple mais son analyse présente certains des comportements émergents les plus extraordinaires jamais vus dans l'histoire de la pensée scientifique / mathématique. Turing a été le premier scientifique / mathématicien à saisir une grande partie de cette signification / puissance / potentiel.