Informatique théorique
Exercice 3:
Système MIU :
Nous avons le système MIU est une suite
de ‘M’,’I’ et ’U’; L0=MU
étant son axiome. L’évolution du système étant basée sur 4 règles qui gèrent
l’extension et la limitation du système. On obtient alors :
-
L0
= {MI}
-
L1
= {MI , MIU , MII}
-
L2
= {MI , MIU , MII , MIUIU , MIIU , MIIII}
-
L3
= {MI , MIU , MII , MIUIU ,
MIIU , MIIII , MIUIUIUIU , MIIUIIU , MIIIIU , MIIIIIIII , MUI , MIU}
-
L4={MI,
MII, MIU, MIUIU, MIIU, MIIII, MIUIUIUIU, MIIUIIU, MIIIIU, MIIIIIIII, MUI,
MIUIUIIUIUIIUIUIIUIUI, MIIUIIUIIUIIU, MIIIIUIIIIU, MUIU, MIUU, MIIIIIIIIU, MIIIIIIIIIIIIIIII,
MUUII, MIIUU, MIUUI, MUIIU, MUIUI}
-
Etc. …
Le jeu du système MIU consiste à vérifier,
à partir des règles de dérivation d’un coté et de l’axiome MI de l’autre, si
tous les assemblages de lettres effectuées à partir de MIU existent. Autrement
dit, il s’agit de savoir si les mots que l’on peut obtenir à partir de ‘M’ , ’I’
et ‘U’ sont des théorèmes du système.
Après quelques tentatives pour trouver
‘MU’ ; on n’est pas arrivé à le trouver. Cependant, on ne peut donner une
preuve formelle sur l’absence de celui-ci. Mais logiquement, ou plutôt
intuitivement, on constate que ‘MU’ ne peut pas être théorème du système pour
les raisons qui suivent :
a- L’assemblage « MU » comporte zéro « I ». Or, zéro est un multiple
de 3.
b- R1
et R2 laissent intact le nombre de « I » autorisé. C’est R3 qui diminue le
nombre de
« I » de 3, sans le changer quant à la divisibilité par 3. R2,
quant à elle, double le nombre de « I ». Et, comme 2n ne peut être divisible
par 3 que si « n » est divisible par 3, R2 ne produit pas de multiple de 3.
Alors, aucune règle ne produit de multiple de 3.
c-L’axiome
« MI » contient un nombre non multiple de 3 de « I », c’est-à-dire un seul « I ».
Par conséquent, aucun théorème ne peut contenir de multiple de 3 de « I », donc
en particulier zéro « I ».
d- Il
est clair que, pour produire la preuve formelle de « MU » dans le système MIU,
il faut supprimer tous les « I ».
Toutes ces constatations, intuitives,
ne constituent pas de preuves formelles, toutefois elles nous donnent une
vision plus claire sur l’existence ou l’inexistence d’un tel ou tel phénomène.