...Tout ce qui est vrai peut-il être démontré ? peut-on trancher de tout ?

Comment tenter de mécaniser un mécanisme d'ordre intellectuel, c'est ce que nous allons introduire au cours de ce thème où nous allons développer deux idées :

• les systèmes formels en tant que mécanisme de manipulation symbolique,
• leur interprétation en tant que moyen de leur associer une signification.

Un développement beaucoup plus détaillée (mais moins digeste) de ces deux aspects du problème peut être trouvé dans le cours Méthodes formelles pour l'informatique donné par l'auteur au CNAM en cycle C.

Préambule

La manipulation symbolique que nous effectuons le plus souvent est le calcul (à ne pas confondre avec les mathématiques).

Commençons par compter

Pour apprendre à compter, quand on est tout petit :

• on commence par apprendre par cœur une suite de mots sous la forme d'une comptine : un, deux, trois, ..., seize
• puis on apprend quelques autres mots : vingt, trente, quarante, ..., cent, mille, ...
• et enfin, on apprend une règle de composition : vingt et un, trente deux, ..., cent mille, ...

Après cela, on dit qu'on sait compter (oralement). Savoir compter représente alors simplement la possibilité de savoir réciter une sorte de poème très ennuyeux mais potentiellement infiniment long. Chaque ligne de ce poème est un nombre. On a très vite inventé des instruments de comptage (le bâton gradué des bergers primitifs, les cordes à nœuds, le chapelet...).

Bien entendu, pour savoir écrire les nombres il va falloir être capable d'associer certains de ces mots à des petits dessins : les chiffres, et une règle de composition associée. On sent bien qu'il ne doit pas être très difficile de concevoir une machine qui saurait compter.

Question : chaque ligne du poème définit-elle un nombre ou simplement nomme-t-elle un nombre défini par ailleurs ?

Savoir calculer

La notion de nombre n'est pas très facile à cerner comme peut l'illustrer la remarque que pourrait faire un enfant à son père :

— Papa, tu me dis qu'il y a 3 pommes sur la table, je vois bien les pommes, mais où est le 3 ?

Question : Si vous deviez définir la notion de nombre (entité qui existe indépendamment de sa représentation), que diriez-vous ?

Ainsi, très souvent la notion de nombre n'est perçue qu'à travers des signes et les manipulations qu'on peut associer à ces signes.

Mécaniser le calcul d'abord, puis des opérations intellectuelles — comme construire une déduction à base de syllogismes par exemple — nécessite la définition d'un processus si simple et si répétitif qu'une simple machine pourra le mettre en œuvre.

Systèmes formels

Un système formel est la définition d'un processus de manipulation de symboles. Il va donc associer :

• des symboles,
• des expressions bien formées,
• des axiomes et
• des règles de déduction.

Question : Essayez d'imaginer deux systèmes formels de la vie courante.
truc : cherchez le symbole et son interprétation.

Ce processus de manipulation de symboles ne présente de l'intérêt que si on peut lui associer une interprétation. C'est grâce à cette interprétation qu'il va nous être utile.

Symbole

Un symbole est un objet auquel nous ne demanderons que deux choses :

• pouvoir le reconnaitre quand on en voit un,
• pouvoir le distinguer d'un autre symbole.

Par nature, si une lettre d'un alphabet est manifestement un symbole, un idéogramme n'en n'est pas vraiment un. On parlera donc de l'alphabet des symboles. Plus généralement, une pierre, un coquillage, une pièce de monnaie peuvent être considérés comme des symboles.

Expressions bien formées

Une expression est constituées de l'association de plusieurs symboles. Elle sera dite bien formées si cette association obéit à un ensemble de règles bien précises. En poursuivant l'analogie linguistique, on appelle souvent l'ensemble de ces règles une grammaire.

Axiomes

Les axiomes sont un ensembles d'expressions bien formées qu'on va sélectionner pour l'intérêt qu'elles représentent. Le choix des axiomes est toujours difficile.

Règles de déduction

Une règle de déduction est un mécanisme à sens unique qui associe une expression bien formée à un ensemble d'expression bien formées. Une règle de déduction peut être considérée comme le modèle d'une relation de causes à effet.

Déduction, hypothèse, et théorème

Une déduction est l'ensemble des expressions qu'on peut construire successivement en appliquant des règles de déduction les unes après les autres.

On peut faire démarrer une déduction de n'importe quelle expression bien formée. Toutes les expressions ainsi obtenues seront dite conséquences de cette expression qu'on nommera hypothèse.

Une déduction qui démarre à partir d'axiomes engendre des expressions qu'on nommera théorèmes.

Prouver qu'une expression bien formée est un théorème revient à vérifier qu'il existe une déduction qui produit cette expression en partant uniquement d'axiomes.

Interprétation, Syntaxe et Sémantique

Interpréter un système formel consiste à donner une signification à ses symboles et à ses théorèmes. Tout le problème réside dans la signification qu'il faut donner à la proposition : donner une signification !

Un système formel engendre un monde syntaxique dans lequel on définit la façon de manipuler des symboles et des expressions. Pour que ce jeu ne reste pas stérile, on lui associe un monde sémantique qui fait que les symboles et les expressions disent quelque chose à celui qui utilise la mécanique du système formel.

L'interprétation est le mécanisme qui permet de passer du monde syntaxique au monde sémantique (et éventuellement réciproquement).

Le passage de l'un à l'autre ressemble tellement à la définition d'une fonction mathématique, qu'on définira une fonction d'interprétation.

Propriétés d'un système formel

Fondamentalement, on ne s'intéresse qu'au monde sémantique, le monde syntaxique n'en est qu'un outil de mécanisation. Il est donc fondamental de s'assurer de l'adéquation entre l'interprétation qu'on peut faire des expressions du monde syntaxique et des propositions concernant des objets du monde sémantique.

En d'autres termes, le système formel n'est construit que pour que ses théorèmes (les expressions porteuses de sens) soient en adéquation avec des propositions sémantiquement correctes.

L'objectif sera toujours d'essayer d'obtenir un système formel complet. Pour étendre l'ensemble de ses théorèmes, nous n'avons que deux méthodes :

• rajouter des règles de déduction,
• rajouter des axiomes.

DANGER ... un axiome ou une règle de trop et le système devient inconsistant  !

Quelques systèmes formels interprétés particulièrement utiles

Parmi les systèmes formels qui ont été conçus, on peut en retenir 3 pour leur importance pratique ou théorique :

• La logique des prédicats : il permet la mécanisation de la rhétorique d'Aristote (discours bien argumenté). Un langage de programmation en est issu : Prolog.
• Le lambda-calcul : il permet la mécanisation du calcul symbolique ou numérique. Toute une famille de langages de programmation en est issu : Lisp, Scheme, ML, Caml, Haskell, Miranda, Hope etc.
• L'arithmétique : il a permis à Gödel de prouver qu'il ne pouvait pas exister de système formel complet de l'arithmétique (théorème de Gödel). En d'autre termes, il n'est pas possible d'étayer les mathématiques en utilisant un raisonnement de type mathématique !

Question : que pensez-vous de la question suivante (paraphrasée d'après le paradoxe du barbier du au mathématicien Bertrand Russell [1] ) :

Comment un humain se sort-il de cette situation ? une machine le pourrait-elle ?

[1] Bertrand Russell, during the course of a long (1872-1970) life, was a noted logician, philosopher, educator, social activist for women's suffrage and later nuclear disarmament, failed politician and reputed philanderer. He was awarded a Nobel prize for Literature, was Wittgenstein's teacher, and served time in prison for his pacifist activities. As Cosma Shalizi notes, they don't make them like that anymore. In my own personal opinion, Russell should be important to the philosophy student for a number of reasons: first, I think that it is impossible to make sense of twentieth-century philosophy without understanding Russell's logical work and the implications of it; specifically, the ideas presented in his Principles of Mathematics (1903) and the later Principia Mathematica (1910-13), co-authored with Alfred North Whitehead. Second, Russell's On Denoting is one of the most famous philosophy essays ever written, and I doubt that one could complete an undergraduate philosophy degree without reading it at least once. Finally, Russell is one of the greatest prose stylists of the twentieth century, and is evidence that one can write important philosophy without being incomprehensible. I recommend that students take a look at his How I Write.