Pourquoi les langages fonctionnels Turing sont-ils complets?

22

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.

Abdul
la source
6
Pas une réponse, mais vous avez mentionné que toutes les versions du calcul lambda ne sont pas Turing Complete. Le calcul lambda simplement typé, et les versions plus fortes de Coq et Agda basées sur la vérification de terminaison, ne sont pas Turing Complete (car ils ont des problèmes d'arrêt décidables). Les langages fortement typés comme Haskell et SML contournent cela en permettant une récursion arbitraire avec un combinateur de points fixes, un terme avec type (a -> a) -> a.
jmite
Il est tellement faux de dire "défini comme étant Turing complet". Pouvons-nous s'il vous plaît changer le titre?
Andrej Bauer
@AndrejBauer Merci pour l'édition du titre, mais je suis curieux de savoir pourquoi c'est ( défini comme Turning Complete ) faux? Est-ce parce que c'est un adjectif? Est-ce que décrire serait un meilleur mot que définir?
Abdul
1
@Abdul Eh bien, le problème est le mot "défini". Si vous dites que "les langages fonctionnels sont définis comme Turing complet", vous dites que la définition de "langage fonctionnel" ou la définition de "Turing complet" indique que les langages fonctionnels sont Turing complets. En fait, aucune définition ne le dit.
Tanner Swett

Réponses:

20

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

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.

babou
la source
Le choix de la machine Turing comme référence, dans la mesure où elle est réellement réalisée, est principalement motivé historiquement: Turing a été le premier à proposer une définition satisfaisante de la calculabilité.
Yuval Filmus
@YuvalFilmus Et pourquoi s'agissait-il plutôt d'une "définition satisfaisante de la calculabilité"?
babou
C'est ce que pensait Gödel. Bob Soare a quelques mots à dire à ce sujet ici: cs.uchicago.edu/~soare/Publications/compute.ps .
Yuval Filmus
@YuvalFilmus Il s'agit de 46 pages. Je veux dire que je donne quelques raisons pour lesquelles cela devrait être plus satisfaisant. Ils peuvent être naïfs. S'il y en a d'autres plus convaincants qui expliquent le succès, c'est à mentionner explicitement.
babou
Regardez la section 3.2. Il y avait des définitions précédentes de la calculabilité, mais elles n'étaient pas convaincantes. Turing a été le premier à être convaincant, du moins pour certaines personnes clés.
Yuval Filmus
21

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.

Yuval Filmus
la source
"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." Mis à part le manque de mémoire infinie, quelles sont les autres raisons pour lesquelles ce n'est pas un bon modèle pour les ordinateurs réels? Aussi, avais-je raison de penser que les langages fonctionnels sont basés sur le calcul lambda?
Abdul
5
λ
11
Langages impératifs ont tendance à permettre des accès de réseau à constante de temps, à C A[x]. Les machines de Turing ne peuvent pas faire cela en temps constant. C'est pourquoi même en informatique théorique, le temps de fonctionnement des algorithmes est analysé sur le modèle de machine RAM plutôt que sur le modèle de machine de Turing.
Yuval Filmus
14
En fait, les machines de Turing sont de bons ordinateurs… sauf que lorsque Turing a écrit son article, «ordinateur» était une description de travail pour un humain travaillant avec un stylo et du papier. La tête de lecture / écriture est un modèle de stylo, la bande est un modèle d'une pile infinie de feuilles de papier (il suffit de les couper en petites bandes et de les coller ensemble), l'alphabet est un modèle de notre alphabet , et les transitions finies sont un modèle du nombre limité de règles que l'on peut garder dans sa tête.
Jörg W Mittag
3
C'était la meilleure idée que j'ai jamais eue sur pourquoi l'enfer turing avait choisi la machine Turing. Je me suis toujours demandé "pourquoi avait-il choisi un modèle de calcul aussi merdique". J'ai toujours pensé que si inventer la théorie du calcul m'avait été laissé (Dieu nous aide; nous ne serions pas très loin) j'aurais probablement choisi un meilleur modèle de calcul. Maintenant j'arrive d'où il venait et ça a tellement plus de sens.
Jake
10

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

David Richerby
la source
Turing-complete pourrait également être nommé en l'honneur de Turing (la personne), qui a proposé la première définition philosophiquement satisfaisante de la calculabilité; ou il pourrait être nommé en l'honneur du document de Turing dans lequel il décrit ce concept.
Yuval Filmus
1
@YuvalFilmus: il pourrait être nommé d'après la mère d'Alan Turing, mais l'affirmation ici est que ce n'est pas le cas ;-)
Steve Jessop
@YuvalFilmus pourrait l'être (cependant, à ma connaissance, non). Mais d'où vient le terme n'a qu'une importance secondaire. Ce qui importe ici, c'est ce que le terme signifie .
David Richerby
2
C'est court et doux, mais peut-être un peu trop court. Que fait une machine Turing? Eh bien, parmi les choses qu'ils "font", il y a la lecture et l'écriture de bandes, ce que les expressions lambda ne font pas.
Theodore Norvell
@TheodoreNorvell Je pense que votre commentaire est similaire à ce que je pensais. Je savais que le calcul lambda et la machine de Turing sont de puissance équivalente, mais de mécanisme différent (et maintenant j'ai appris qu'il y en a d'autres), mais je me demandais si le terme "complétude de Turing" était en quelque sorte spécial à la machine de Turing, ou si c'était juste un nom.
Abdul
6

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.

Peter Taylor
la source
0

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.

vzn
la source
en d'autres termes, on pourrait dire que Turing a été le premier à identifier / "reconnaître" l'importance du phénomène d'exhaustivité de Turing et à son tour, CS "le reconnaît" pour cette réalisation monumentale grâce à l'utilisation du terme.
vzn
X