INFORMATIQUE Principes
Algorithmes et décidabilité
Un algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, en un nombre fini d'étapes, à un certain résultat, et cela indépendamment des données ; par exemple, l'algorithme de l'addition permet de faire l'addition de deux nombres quelconques en partant des chiffres les plus à droite et en opérant de droite à gauche. Un algorithme étant une description de la suite des opérations à faire, il est clair que la manière de le rédiger dépendra du dispositif (homme ou machine) chargé de l'exécuter et qu'un algorithme écrit en turc par exemple n'est pas un algorithme pour celui qui ignore cette langue. De ce point de vue, un programme destiné à un ordinateur est très précisément un algorithme, et un langage de programmation est un langage permettant d'écrire un algorithme qu'un ordinateur saura exécuter. De ce même point de vue, l'ensemble des règles d'un automate à pile de mémoire est un algorithme permettant de savoir si une phrase écrite sur le ruban d'entrée appartient ou non à un certain langage.
Si l'algorithme ne permet pas d'arriver au résultat en un nombre fini d'étapes, on dit que l'on a un pseudo-algorithme. Pour déceler un pseudo-algorithme, il faudrait pouvoir construire un algorithme qui, appliqué à un quelconque pseudo-algorithme, permettrait de trancher la question. Malheureusement, et ce résultat est d'une extrême importance, on démontre qu'il est impossible de construire un tel algorithme ; ce problème est indécidable. En termes de programmation, cela revient à dire qu'il est impossible d'écrire un programme qui, prenant un autre programme comme donnée, permettra de savoir si ce programme fournira des résultats au bout d'un temps fini.
Le caractère indécidable de certains problèmes n'autorise aucune spéculation sur les limites de l'esprit humain ou sur la vanité de toute logique. Il s'agit là de démonstrations de caractère technique à l'intérieur d'un système de logique et elles n'ont pas plus de conséquences « philosophiques » que le théorème de Pythagore.
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Jacques HEBENSTREIT : ingénieur Supélec, docteur ès sciences, lauréat de l'Académie des sciences, consultant à l'O.C.D.E.
Classification
Médias
Automate à nombre fini d'états
Encyclopædia Universalis France
Automate à pile de mémoire
Encyclopædia Universalis France
Autres références
-
PHYSIQUE - Physique et informatique
- Écrit par Claude ROIESNEL
- 6 760 mots
La révolution informatique est de nature technologique. Les physiciens sont associés à toutes les étapes de son développement. Les technologies incorporées dans les premiers ordinateurs avaient été inventées pour les besoins de la recherche en physique nucléaire. Le convertisseur analogue-digital,...
-
AFFICHE
- Écrit par Michel WLASSIKOFF
- 6 817 mots
- 12 médias
Dansles années 1990, l'affiche est de plus en plus souvent conçue sur écran, la publication assistée par ordinateur (P.A.O.) permettant l'association des textes et des images. La mise au point du langage Postscript conduit à la création de caractères haute résolution et le dessin de lettres connaît... -
AIKEN HOWARD HATHAWAY (1900-1973)
- Écrit par Bernard PIRE
- 506 mots
L’Américain Howard Aiken fut un des pionniers de l'informatique, concepteur de l'IBM Automatic Sequence Controlled Calculator (ASCC) encore appelé Harvard Mark I.
Après avoir suivi les cours d'une école technique tout en travaillant la nuit, Howard Hathaway Aiken, né le 9 mars 1900 à...
-
ALGORITHME
- Écrit par Alberto NAIBO et Thomas SEILLER
- 5 919 mots
- 4 médias
La notion d’algorithme a envahi nos discours et nos pratiques, en raison surtout de la diffusion massive d’applications informatiques dédiées à l’exécution automatisée de certaines tâches, ou à la résolution de certains problèmes. On trouve en effet les algorithmes non seulement dans de nombreux domaines...
-
APPLE
- Écrit par Pierre MOUNIER-KUHN
- 2 547 mots
- 2 médias
Archétype des start-up de la Silicon Valley, la société américaine Apple, fondée en 1976, a gagné fortune et célébrité par ses innovations de rupture, de l’ordinateur Macintosh au téléphone portable iPhone et à la tablette numérique iPad. Associée au talent visionnaire de son président historique,...
- Afficher les 148 références
