Architectures des systèmes informatiques
CHAPITRE 1
Origine et évolutions des architectures
Année 2002-2003
Suite
N°3...
Toute connaissance
humaine peut être décrite à l'aide d'un ensemble d'énoncés,
chacun d'eux parfaitement compréhensible par quiconque et ne donnant
lieu, quel que soit son lecteur, qu'à une unique interprétation.
Platon
1.3 LES ANNÉES 1930
La passion du calcul mécanique
Les années trente
sont celles d'une explosion des théories en matière de calcul.
On trouvera un court aperçu de travaux théoriques récents
dans le § 1.9. Ces théories
qui aboutissent toutes à définir un système formel,
ont été établies pour répondre à une
question :
«Qu'est
ce qui peut être calculé mécaniquement en un
temps fini et qu'est ce qui ne le peut pas ?»
Parmi ces théories, citons :
Il faut remarquer ici que tous ces systèmes formels ont été montrés équivalents entre eux et donc à celui de Turing qui définit les fonctions T-calculables. La classe des fonctions calculables, objet mathématique unique, est ainsi définissable indifféremment par plusieurs théories sans rapport structurel entre elles. Ceci intrigue encore car se produisant à l'intérueur des mathématiques.
Des observations à première
vue comparables mais qui ne le sont pas, sont faites en matière
de relations entre mathématiques et physique. Ce sont :
.le polymorphisme mathématique
de la physique; plusieurs structures mathématiques très
différentes rendent compte avec la même qualité d'un
même phénomène physique, un exemple est la
théorie
de la gravitation de Newton;
.la plurivalence physique
des mathématiques; la même structure mathématique
s'applique à des domaines très différents de la physique,
par exemple l'équation aux dérivées partielles de
Poisson gouverne l'électrostatique, la diffusion de la chaleur,
l'équilibre d'une membrane élastique déformée,
etc.
Le lecteur fera ici une première observation : Les fonctions calculables n'ont pas une définition intrinsèque. Elles sont les fonctions qui peuvent effectivement être calculées par un des systèmes précédents. En d'autres termes on peut dire qu'une fonction est calculable si on peut effectivement la calculer avec un outil pré défini.
Une NOTE COMPLÉMENTAIRE ci-après présente brièvement l'origine et le pourquoi de ces théories.
Il nous suffit pour l'instant de considérer qu'elles ont été construites pour étayer ou réfuter trois propriétés générales des théories axiomatiques, que l'on supposait presque toujours vraies jusqu'à leur réfutation. On peut les énoncer comme suit, en utilisant le mot théorie pour théorie axiomatique :
AVERTISSEMENT :
Les définitions qui suivent ne sont pas des définitions mathématiques. Le lecteur trouvera dans des ouvrages spécialisés la ou les définitions utilisées par tel ou tel. Dans ce cours d'informatique, nous tentons de rendre compréhensible les travaux évoqués et non d'apporter des démonstrations.
Consistance : une théorie est consistante si l'on peut prouver, au moyen d'une théorie plus faible, qu'elle ne peut pas produire d'énoncé contradictoire. La théorie sera ainsi exempte de contradictions.
Complétude :
une théorie est complète si tout énoncé interne
dont les variables sont quantifiées peut être soit démontré
soit réfuté. Alors, la théorie est complète
car aucun de ses énoncés ne reste dans l'incertitude, on
dit aussi qu'elle ne contient pas d'énoncé indécidable.
On peut dire qu'une théorie
incomplète ne prouve pas tous ses théorèmes.
Deux situations d'incomplétude
méritent examen. La plus simple est que l'on connaisse un énoncé
indécidable. Alors la théorie n'est pas complète.
L'autre est que l'on ait prouvé seulement la possibilité
d'existence d'un tel énoncé.
Dans les deux cas, qu'un énoncé
soit connu ou simplement que l'on sache qu'il en existe au moins un ne
dit pas comment établir la réponse, ce que l'on nomme le
problème de la décision.Décidabilité
: une théorie est décidable si l'on peut concevoir
une méthode qui, pour tout énoncé de la théorie,
mène à décider s'il est démontrable ou ne l'est
pas. Une théorie incomplète est évidemment indécidable.
| Kurt Gödel (1906-1978), mathématicien et logicien, né à Brünn dans l'empire d'Autriche-Hongrie, aujourd'hui Brno en république Tchèque. En 1931, il a montré qu'il ne peut pas y avoir de certitude qu'une théorie soit consistante ni complète. En termes plus ordinaires, une théorie axiomatique peut contenir des énoncés dont on ne pourra jamais démontrer s'ils sont vrais ou faux. Ces énoncés, s'ils existent, ne sont pas indéterminés, ils sont effectivement ou vrais ou faux, mais il n'est pas possible de démontrer ce qu'ils sont. |  |
Le premier apport d'Alan Mathison Turing (1912-1954).
A. Turing connaît bien les travaux de Russell et de Gödel. Il est élève de Church. Il choisit de commencer par l'examen d'un énoncé équivalent à la proposition de décidabilité, qui a été donné par Max Newman : «Existe-t-il un procédé mécanisable qui détermine si une proposition est démontrable ou ne l'est pas ?»
Entre 1935 et 1937, Turing définit la «machine» qui porte son nom et démontre qu'elle peut réaliser toutes les opérations applicables aux nombres entiers. K. Gödel avait montré auparavant que la démonstration en arithmétique se ramène à calculer sur des nombres (cf. plus loin, les nombres de Gödel). Turing démontre en plus que les théories axiomatiques et en particulier l'arithmétique ne sont pas décidables. Il publie en 1936, son article célèbre sous le titre: «On Computable Numbers, with an Application to the Entscheidungs problem», c'est l'application au problème de la décision. Il établit... que l'on ne peut pas décider. Autrement dit, il n'existe pas d'algorithme permettant de savoir, d'une machine de Turing donnée, si elle fonctionnera indéfiniment sur une bande initialement vide, ou si elle atteindra un état final. On trouvera un plus long développement sur la machine de Turing et les conséquences des théories, dans le § 2.1.1.
Le premier apport d'Alonzo
Church (1903-1995) est comparable à celui d'Alan Turing. Il
construit ce qu'il appelle le l-calcul.
Il établit un théorème important : Il n'est pas possible
d'envisager une technique générale pour déterminer
la vérité ou la probabilité de toutes les propositions
de l'arithmétique. En cela, l'arithmétique diffère
du calcul des propositions, décidable par tables de vérité,
mais non du calcul des prédicats dans son ensemble. Par ce biais
aussi, le projet qu'avait formé Hilbert d'introduire des démonstrations
effectives en mathématiques devient irréalisable.Le
deuxième apport des deux mêmes est de nature différentes.
On l'énonce en général
sous la forme de deux thèses, ce qui veut dire qu'il s'agit de proposition
non démontrées et peut être non démontrables.
On trouve d'autres énoncés de ces deux thèses séparées ou réunies sous le nom de thèse de Church-Turing ainsi que Kleene les a réunies en 1967, sous des énoncés divers comme :
«TMs (Turing machines) can compute every function computable in any thinkable physical model of computation. This is not a mathematical result because the notion of model is not formally specified. But the long history of investigations of ways to design real and ideal computing devices makes it very convincing.» (Leonid Levine, Berkeley) [LEV86].
«Les machines de Turing peuvent calculer toute fonction qui serait calculable dans tout modèle de calcul envisageable physiquement. Ceci n'est pas un résultat mathématique car la notion de modèle n'y est pas spécifiée de façon formelle. Toutefois, l'histoire, maintenant longue, des travaux sur les moyens de calcul tant réels qu'idéaux la rend très convaincante.»
Le propre d'une thèse est de n'être pas démontrable sauf à construire une théorie dont elle serait un théorème. La rhèse de Church-Turing a le statut de définition de la notion jusqu'alors intuitive d'algorithme : un algorithme est une machine de Turing.
Comment se convaincre de sa validité ? Elle est maintenant largement admise et de nombreux arguments vont dans son sens :
| En 1936, il est
étudiant en génie électrique au M.I.T. à Boston.
Dans son mémoire de maîtrise, il prouve que les circuits à
base de relais et d'interrupteurs sont modélisables par l'algèbre
de Boole. C'est là un acquis essentiel pour les relais et pour les
autres techniques fonctionnellement identiques :
Une triode fonctionne comme un
relais.
Le texte fondateur : «A
symbolic analysis of relays and switching circuits», est
publié en 1938 dans les Transactions of IEE [SHA38].
En 1940, il soutient une thèse sur un sujet plus large. On mentionnera
plus loin ses travaux des années 40
sur les transmissions et sur l'échantillonnage.
|
 |
Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 1
Origine et évolutions des architectures
Année 2002-2003
