[le pavé, le pavé !]
Envie d’ouvrir sur un sujet qui me turlupine, pas trop clair sur mes intentions, qui m’intrigue et me fascine. A notre époque de science, d’information, de conjecture en tout sens, de pensée formelle (comme les gens qui écrivent « cuisine » sur le mur de leur cuisine oO), de la pensé occidentale, explicative, théorique, analytique (je m’emballe un peu), j’aime me confronter à ce petit problème qui je trouve se révèle amusant. On peut le voir comme un jeu, et aussi comme une
limite frontière au formalisme. Il semblerait que la nature, bien faite, ne permette pas au langage (formel) de tout définir de façon claire et précise, tout du moins dans le cadre de cette « pensée occidentale et bientôt mondiale » de ceux qui aiment écrire cuisine dans leur cuisine. (En vérité, ça m’amuse plus que ça m’effraie, mais je trouve ça bizarre d’écrire cuisine sur les murs de sa cuisine, ça fait étiquette fonctionnelle définissant l’utilité du lieu et que cela serait "plus" que les ustensiles en présence et les corps qui remuent dedans pour s’en servir. On dirait qu’avec cuisine écrit sur le mur, « tout est dit » alors qu’en fait « rien n’est fait » - Bon peut être aussi que les amateurs de mots et de polices trouvent ça beau, ou cool, et que c’est moi du coup qui "analyse" et tourne en rond un peu trop oO )
Donc voilà, j’ai envie de parler de cette chose (le problème du castor affairé,) qui présente quelque chose de parfaitement défini mais non calculable. En somme une cuisine, mais sauf que là, d’une façon remarquable, personne n’arrivera jamais à écrire cuisine sur le mur pour dire : Ceci est une cuisine. Ceci est une cuisine. Ceci est une cuisine. Ceci est ça.
Cadre du problème et ustensile :Commençons par prendre un ruban de papier, découpé en cases identiques (autant que l’on veut). Prenons un alphabet, c'est-à-dire un ensemble de symboles, composé de seulement deux symboles, disons « 0 » et « 1 » dans notre cas précis du problème. Dotons-nous d’une tête de lecture/écriture capable de parcourir le ruban case par case (qu’on aura initialisé par un zéros dans chacune des cases), dans les deux sens, lire et écrire dans une case et seulement une case à la fois, et enfin permettons nous de donner des instructions à cette machine. (car elle ne vas pas parcourir/lire/écrire le ruban comme elle veut, c’est nous qui allons lui dire comment parcourir ce ruban)
Pour donner des instructions, il nous faut un état à étiqueter à la tête (on pourrait appeler les états Cuisine, Salle de bain, chambre, chiotte, mais pour des raisons de simplicité et pour faire plus sérieux, nous les appellerons état « 1 » état « 2 », etc etc. )
Petit schéma représentatif :
(marrant la forme de la première image)
Exemple tout de suite : disons qu’initialement, la tête est dans l’état « 1 » et sur la case numérotée 1 du ruban ( rappel : toutes les cases dans notre cas précis sont initialisées avec 0, la première case aussi contient donc 0)
On peut définir par exemple l’instruction suivante lorsque la tête est dans l’état 1 (c'est-à-dire l’instruction que doit suivre la tête si elle est dans l’état 1):
Etat 1 :
(par exemple)
- si je lis un « 0 », j’écris un « 1 » dans la case ou je suis, je me déplace a droite, et je passe dans l’état 2
- si je lis un « 1 », j’écris un « 1 » dans la case ou je suis, je me déplace pas, et je passe dans l’état 3
(les instruction ont toute cette forme : si je lis « a », j’écris « b » (b peut etre égale a a), je me déplace a Gauche ou droite ou pas, et je passe dans l’état n (ou STOP pour finir le travail). Ça peut se formaliser par exemple dans notre cas d’instruction sur l’état 1 par :
Etat 1 :
0-1-D-2
1-1-X-3
Vu qu’il n’y a que deux symbole possible, la tête sait toujours quoi faire si elle se trouve dans l’état 1 (elle sait ce qu’elle doit faire si elle lit un « 0 », ou si elle lit un « 1 ». L’on peut voir qu’à la fin de l’instruction, la tête passe dans l’état 2 ou 3 selon ce qu’il y avait dans la case initialement (au début il y a zéros mais en activant la mécanique des instructions, rien ne nous dit qu’on ne va pas un jour être dans l’état 1 et lire un 1 sur une autre case). Il faut donc définir une instruction pour les Etat 2 et 3. Si les instructions des états 2 et 3 ramènent vers les états 1,2,3 alors la machine est parfaitement définie et saura toujours quoi faire.
Etat 2 :
(par exemple)
Si je lis un zéro, j’écris 1, je vais à gauche, je passe dans l’état 1 (0-1-G-1)
Si je lis « 1 », j’écris 1, je vais a droite, je reste dans l’état 2 (1-1D-2)
Etat 3
(par exemple)
0-1-G-2
1-1-D-STOP
Cette machine, dotée d’instructions et donc capable d’écrire des « 1 » sur des zéros, ou des « 0 » sur des « 1 » ou des « 1 » sur des « 1 » ou des « 1 » sur des « 0 », et la manière dont elle va faire cela (déplacement, changement d’état) est parfaitement définie par le jeu d’instruction. Quelque soit l’état dans lequel se trouve la tête, elle sait ce qu’elle doit faire en fonction de ce qu’elle lit sur la case où elle se trouve et cela de façon déterministe. Cette machine est un cas particulier qui se définit de façon plus générale par Machine de Turing. Ici on peut parler de machine de Turing binaire (car l’alphabet est composé de 0 et 1) à 3 états (car on a 3 états + l’état final STOP).
(La machine de Turing est un modèle mathématique inventé par Turing pour tenter de définir la notion de calculable – Calculable au sens large, c'est-à-dire capable de transformer une information formelle en une autre. C’est aussi le modèle conceptuel de l’ordinateur. Tout ce que sait faire un ordinateur, une machine de Turing sait le faire, pour peu qu’on la dote du bon jeu d’instructions – Créer le jeu d’instructions, c’est ce qu’on appelle programmer)
Cas de l’arrêt de la machine : Une remarque sur l’arrêt de la machine. Imaginons la machine de Turing binaire a 1 état, initialisé avec un ruban remplit de zéros, avec l’instruction suivante :
Etat 1 :
Si je lis 0, j’écris 1, je vais a droite, et je reste dans l’état 1 (0-1-D-1)
Si je lis 1, j’éecris1, je vais a gauche, je passe dans l’état STOP.(1-1-G-STOP)
Sur un ruban remplit de zéro, cette machine ne va jamais s’arrêter et remplir le ruban d’une infinité de 1. Elle va lire un zéro, écrire un dans la case, aller à droite et rester dans l’état 1. Sur la nouvelle case, elle lit un zéro, écris 1, va à droite et reste dans l’état 1, etc etc etc… elle n’atteindra jamais l’état STOP.
Dans ce cas on dit simplement que la machine ne s’arrête pas. Dans le cas contraire on dit qu’elle s’arrête.
Problème du castor Affairé : Soit une machine de Turing binaire à N états avec un ruban infini entièrement initialisé avec des zéros, on appelle Sigma(N) la fonction qui a N associe le nombre de 1
maximale que la machine peut écrire avec
le meilleur jeu d’instruction possible sur ces N états
mais qui s’arrête au bout d’un certain temps (c'est-à-dire que la machine atteint un jour l’état STOP, donc exit les instructions qui font que la machine ne s’arrête jamais et n’atteigne pas l’état STOP.)
Ben voilà, on vient de tomber sur un problème où personne ne sera jamais assez fort pour ce calcul. Personne ne pourra donner l’expression de cette fonction sigma, c’est démontré. La fonction sigma est démontré incalculable, pourtant ce chiffre existe bel et bien pour chaque N. chaque sigma(n) est un nombre entier < infini (la machine s’arrête donc elle peut pas en écrire ad vita eternam)
On connait sigma(1) c’est 1. Sigma(2)=4, sigma(3)=6 et sigma(4)=13. Pour sigma(5) on sait que ce nombre est supérieur à 4 098 et pour sigma(6) on sait qu’il est supérieur à 3,5×10^18 267 ce qui est au passage un nombre monstrueux battant largement le nombre d’atomes dans l’univers (qui lui est de l’ordre de 10*10^80 il me semble…).
Pire on sait qu’aucun langage formel n'est à même de décrire cette fonction quelles que soient les astuces symboliques pouvant décrire les nombres. (C’est-à-dire qu’il n’existe même pas un formalisme de récurrence entre les sigmas(n) eux même). C’est une fonction plus croissante que n’importe quelle fonction croissante que l’on peut écrire mathématiquement. Bref c’est incalculable.
Et ben moi, ça me broute le chou de savoir que cette fonction est parfaitement définie mais quelle n’est pas exprimable par aucun moyen que ce soit. Et en même temps je me dis que si un truc aussi simple (dans le sens élémentaire : des histoires de cases et de jeux d’instruction qu’un enfant de 8 ans pourrait effectuer avec un papier et une feuille) échappe à la raison ben c’est cool, y’a un coté rassurant non ?
Tout n'est pas mesurable, pas quantifiable et donc pas explicable dans le sens qui me parait aujourd’hui être l'unique valeur mise en avant. Le scientifiquement démontré, le prouvé, le raisonnement, le déterminisme, l'assurance de maîtriser notre compréhension de tout. Ceci n'est pas réellement une dent contre le formalisme, j'adore ça car il est arrivé à un point où il s'interroge lui même et sur ses
limites frontière, il les met en évidence par ses propres moyens, avec sa force dure comme le diamant qu'on lui connaît et qui est réelle. Cette frontière là est fascinante je trouve.
Bien sûr cela peut sembler très abstrait une telle machine. Pourtant depuis les années 50 cette machine abstraite et passée dans le concret avec l'ordinateur et autres cas, et par là même, les propriétés qui s'en dégagent viennent d’être injectées du pur symbolisme vers un constat de la matière. Les propriétés des machines de turing et leur limite sur leur compréhension sont les même que les propriétés de n'importe quelle machine effectuant des calculs et constituée de matière.
Il n'est pas rare dans la théorie de la calculabilité d'invoquer un "Oracle" dans certaine démonstration ou résultat, une entité symbolique qui connaît la réponse que l'on ne pourra jamais atteindre nous (car cette réponse existe et est donc définie mais on ne la connaît pas, ou si on la connaît, c'est qu'on nous l'aura donnée ou qu'on l'aura "devinée" puisque dans le cas de non-calculable, aucune expression formelle ne sera suceptible de décrire la façon dont on l'obtient).
Je me demande quel rapport entretient L'oracle à la matière, au monde tangible que nous soupçonnons.
Accueil 
dans ton turlupinage ! Et bravo à ceux qui suivent ! 
