4. Expressivité des langages de programmation
De nombreux langages de programmation sont utilisés en pratique, mais on peut se demander si ils sont tous aussi “puissants”. C’est ce à quoi nous allons nous intéresser dans cette partie. Dans cette première vidéo, on utilise le langage Gobot pour expliquer le concept d’expressivité.
Dans cette deuxième vidéo, nous nous intéressons au concept d’“expressivité absolue”.
- Fiche scientifique :
Avez-vous retenu ?
- Est-ce que tous les langages de programmations offrent les mêmes possibilités ?
- Le langage Gobot peut-il réaliser tous les algorithmes ?
- Existe-t-il des langages avec lesquels il est possible d’exprimer n’importe quel algorithme ?
- L’expressivité d’un langage de programmation est-elle le seul facteur pour choisir un langage ?
- Sous quelles conditions un langage de programmation est-il Turing-complet ?
- Non, on a vu dans cette partie qu’ils peuvent avoir des expressivités différentes et ne permettent pas la réalisation de certains algorithmes. Voir l’exemple dans la 2ème question.
- Non, effectivement il est incapable d’additionner deux piles de gobelets quelconques par exemple à moins de le complexifier.
- Oui, c’est ce qui a été prouvé par Turing en 1936 et ces langages sont appelés en son honneur des langages Turing-complets.
- Non, en effet même deux langages Turing-complets vont présenter des différences assez significatives selon d’autres points de vue, c’est ce qu’on va voir plus en détail dans la partie suivante.
- À partir du moment ou un langage est capable de réaliser les 4 opérations mathématiques élémentaires, de réaliser des tests logiques (si… alors..) et de répéter une partie de code autant de fois que voulu, on est en fait théoriquement capable d’exprimer tout algorithme dans ce langage.
Pouvez-vous définir :
- Expressivité d’un langage
- Turing-complet
(Les réponses se trouvent dans le glossaire.)
Notions importantes :
- Les langages de programmation diffèrent selon leur expressivité.
- Des langages capables d’exprimer tous les algorithmes existent, et la majorité des langages de programmation modernes en font partie.
Question d’approfondissement :
Nous avons vu que la plupart des langages modernes étaient Turing-complets. Mais alors quels sont les deux facteurs limitant fortement les exploits réalisables par un ordinateur ?
Que les langages soient Turing-complet ne signifie pas que l’on peut tout faire !! En effet, les programmes sont à partir d’un certain point, limités par la puissance de calcul ainsi que par la taille de la mémoire des ordinateurs.