Modèles de calcul
De nombreux cadres formels définissent ce que signifie calculer, allant de la réécriture de fonctions du calcul lambda aux circuits booléens et aux systèmes quantiques, et la comparaison de leur puissance révèle quels modèles sont équivalents et lesquels diffèrent réellement.
Definition
Un modèle de calcul est un cadre abstrait précis qui spécifie quelles opérations sont autorisées et comment un calcul se déroule ; différents modèles peuvent calculer la même classe de fonctions tout en différant par leur concision, leur parallélisme ou les ressources qu'ils rendent explicites.
Scope
Ce domaine couvre le calcul lambda et les modèles fonctionnels, les fonctions récursives et les machines à registres, les circuits booléens et la complexité des circuits, ainsi que le calcul quantique, examinant comment chaque modèle exprime les algorithmes, comment leur puissance de calculabilité est liée par la thèse de Church-Turing, et comment leur efficacité peut diverger.
Sub-topics
Core questions
- Quelles sont les différentes manières de formaliser la notion de calcul ?
- Quels modèles sont équivalents quant aux fonctions qu'ils peuvent calculer, et pourquoi ?
- Comment les modèles diffèrent-ils lorsque l'efficacité, le parallélisme ou la réalisabilité physique entrent en jeu ?
- Un modèle physiquement motivé, tel que le calcul quantique, peut-il dépasser l'efficacité classique ?
Key theories
- Équivalence selon la thèse de Church-Turing
- Le calcul lambda, les fonctions récursives, les machines à registres et les machines de Turing calculent tous exactement la même classe de fonctions, cette convergence fonde l'identification du calcul avec la calculabilité de Turing.
- Divergence en efficacité
- Les modèles qui s'accordent sur la calculabilité peuvent différer fortement en termes de ressources : les circuits exposent le calcul parallèle et non uniforme, et les modèles quantiques semblent offrir des accélérations, de sorte que le choix du modèle est très important pour la complexité même lorsqu'il ne l'est pas pour la calculabilité.
Clinical relevance
Différents modèles éclairent différents aspects du calcul réel : le calcul lambda est la base théorique des langages de programmation fonctionnels, les circuits modélisent le matériel et le calcul parallèle, les machines à registres reflètent les processeurs conventionnels, et les modèles quantiques guident la conception du matériel et des algorithmes quantiques émergents.
History
Dans les années 1930, le calcul lambda de Church, les fonctions récursives de Gödel et Kleene, et les machines de Turing furent chacun proposés puis démontrés équivalents. Des modèles ultérieurs ont ajouté de nouvelles dimensions : la complexité des circuits a formalisé le calcul parallèle et matériel, et la proposition de Feynman en 1982 de simulation quantique a semé les graines du modèle de calcul quantique.
Key figures
- Alonzo Church
- Alan Turing
- Stephen Kleene
- Richard Feynman
Related topics
Seminal works
- church1936
- sipser2013
- aroraBarak2009
Frequently asked questions
- Pourquoi étudier de nombreux modèles s'ils calculent les mêmes fonctions ?
- L'équivalence ne vaut que pour ce qui peut être calculé en principe. Différents modèles facilitent l'expression ou l'analyse de différentes choses : le calcul lambda clarifie la programmation fonctionnelle, les circuits révèlent le parallélisme et les coûts matériels, et les modèles quantiques capturent les phénomènes physiques, donc chacun est la bonne approche pour différentes questions.
- Tous les modèles de calcul sont-ils équivalents ?
- Tous les modèles classiques raisonnables calculent la même classe de fonctions, ce qui soutient la thèse de Church-Turing. Mais ils peuvent différer grandement en efficacité, et les modèles qui exploitent des ressources différentes, telles que la superposition quantique, peuvent résoudre certains problèmes plus rapidement même en calculant les mêmes fonctions.