INFORMATIQUEPrincipes

Carte mentale

Élargissez votre recherche dans Universalis

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.

1  2  3  4  5
pour nos abonnés,
l’article se compose de 5 pages

Médias de l’article

Automate à nombre fini d'états

Automate à nombre fini d'états
Crédits : Encyclopædia Universalis France

dessin

Automate à pile de mémoire

Automate à pile de mémoire
Crédits : Encyclopædia Universalis France

dessin

Afficher les 2 médias de l'article


Écrit par :

  • : ingénieur Supélec, docteur ès sciences, lauréat de l'Académie des sciences, consultant à l'O.C.D.E.

Classification

Autres références

«  INFORMATIQUE  » est également traité dans :

INFORMATIQUE - Vue d'ensemble

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 162 mots

Le mot informatique – contraction de information et automatique – semble avoir été créé en Allemagne par Karl Steinbuch qui utilisa le terme Informatik dans un article publié en 1957 intitulé « Informatik : Automatische Informationsverarbeitung » (Informatique : traitement automatique de l'information). En mars 1962, Philippe Dreyfus, […] Lire la suite

INFORMATIQUE - Histoire

  • Écrit par 
  • Pierre GOUJON
  •  • 4 469 mots
  •  • 2 médias

Un usage bien établi associe le mot « informatique » à l'ensemble des opérations de traitement de l'information effectuées à l'aide de machines électroniques perfectionnées conçues par essence pour aider l'être humain à surmonter au mieux l'opposition classique qui sépare dans ses activités la compétence de la performance. Les premières machines ont eu effectivement pour mission de pallier les ins […] Lire la suite

INFORMATIQUE - Ordres de grandeur

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 2 645 mots
  •  • 2 médias

Dans son énoncé le plus général, la loi de Gordon E. Moore (né en 1929), cofondateur d'Intel en 1968, indique que la capacité de calcul et de stockage d'informations d'un dispositif informatique d'un coût donné double tous les dix-huit mois, ce qui revient à affirmer que cette capacité est multipliée par dix tous les cinq ans. Dans cinq ans, votre ordinateur devrait ainsi disposer d'un disque dur […] Lire la suite

PHYSIQUE - Physique et informatique

  • Écrit par 
  • Claude ROIESNEL
  •  • 6 728 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, les systèmes de stockage de l'information ou les premiers […] Lire la suite

AFFICHE

  • Écrit par 
  • Michel WLASSIKOFF
  •  • 6 815 mots
  •  • 12 médias

Dans le chapitre « L'avènement du numérique »  : […] Dans les 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 un formidable engouement. Autour de la revue Emigre , en Californie, surgit une New typography […] Lire la suite

AIKEN HOWARD HATHAWAY (1900-1973)

  • Écrit par 
  • Bernard PIRE
  •  • 498 mots

Un des pionniers de l'informatique, concepteur de l'I.B.M. Automatic Sequence Controlled Calculator (A.S.C.C.) 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 à Hoboken (New Jersey), est engagé à la compagnie du gaz de Madison, ce qui lui permet de suivre une formation d'ingénieur électricien à l' […] Lire la suite

APPLE

  • Écrit par 
  • Pierre MOUNIER-KUHN
  •  • 2 539 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, Steve Jobs (1955-2011), elle est devenue une entreprise de taille mondiale, l’une des plus importante […] Lire la suite

ARCHÉOLOGIE (Traitement et interprétation) - La photogrammétrie architecturale

  • Écrit par 
  • Jean-Paul SAINT AUBIN
  •  • 5 210 mots
  •  • 1 média

Dans le chapitre « L'analyse du couple photogrammétrique : la restitution »  : […] Dans l'appareil de restitution, les photographies sont observées en couple, en « stéréoscopie ». Le phénomène physiologique de la stéréoscopie renvoie à la vision naturelle de l'homme qui enregistre, avec ses yeux, deux images que le cerveau fusionne pour lui permettre d'avoir une vision en relief. Artificiellement, deux photographies prises de deux points de vue différents, et observées l'une pa […] Lire la suite

ARCHITECTURE CONTEMPORAINE - Construire aujourd'hui

  • Écrit par 
  • Antoine PICON
  •  • 6 516 mots
  •  • 3 médias

Dans le chapitre « Un outil d'aide à la conception »  : […] Quoique limitée, du moins pour l'instant, la généralisation de l'outil informatique influence l'évolution de l'architecture. Elle tend à promouvoir des formes mouvementées que certains critiques n'hésitent pas à comparer à un nouveau baroque. Sans forcément souscrire à cette analyse, des théoriciens et des praticiens de l'architecture comme l'Américain Greg Lynn se sont fait les hérauts d'une nou […] Lire la suite

ARCHIVAGE NUMÉRIQUE

  • Écrit par 
  • Claude HUC
  •  • 4 763 mots
  •  • 2 médias

Les outils informatiques ne cessent d'évoluer : les ordinateurs changent et leur puissance augmente, les systèmes d'exploitation et les logiciels se renouvellent sans cesse et sont à chaque fois différents, les supports de stockage existants disparaissent au profit de technologies nouvelles. Ainsi, de multiples documents sont incompatibles avec les moyens techniques qui se sont développés postéri […] Lire la suite

Voir aussi

Pour citer l’article

Jacques HEBENSTREIT, « INFORMATIQUE - Principes », Encyclopædia Universalis [en ligne], consulté le 22 janvier 2021. URL : https://www.universalis.fr/encyclopedie/informatique-principes/