Une machine de turing à accélération
Je propose ici une machine de Turing révolutionnaire, dont la vitesse de calcul augmente avec le temps. L'existence de cette machine de Turing pose des questions sur la nature de l'intelligence.Principe
Une machine de Turing (MdT) est définie par un tableau ou programme qui, pour chaque état et chaque symbole lu, donne le symbole à écrire, la direction (gauche ou droite) du déplacement de la tête sur le ruban, et le nouvel état. Par convention, l'état zéro est l'état "stop" et la machine démarre dans l'état 1.On ne s'intéresse ici qu'aux machines binaires (c'est à dire disposant de deux symboles : 0 et 1) et qui partent d'un ruban initialement vierge (ne contenant que des zéros). Ceci ne réduit en rien la généralité : toute MdT peut être simulée par une MdT binaire, et les premières instructions de la machine peuvent être consacrées à l'écriture d'une chaîne quelconque sur le ruban, à partir de laquelle on enclenchera le "vrai" programme.
La définition d'une MdT est opératoire, mais peu efficace
: pour réaliser rapidement des simulations de MdT sur un ordinateur
quelconque, on est souvent amené à "compiler" le programme
de la Mdt. Par exemple soit la MdT suivante :
état symbole lu zéro symbole lu 1
e1 1,d, e2 1,g,e1
e2 1,g,e1 1,d,0 (stop)
On peut voir que lorsque la tête se trouve au début d'une séquence "00" dans l'état 1, ce que je note ainsi (les crochets [] donnent la position de la tête sur le ruban) :
1:...[0]0..., tout d'abord elle écrit "1", puis va a droite et passe dans l'état 2 :
2:...1[0]..., ensuite elle écrit "1", va à gauche et passe dans l'état 1 :
1:...[1]1..., ensuite elle réécrit un 1 par dessus celui existant, va a gauche et passe (reste) dans l'état 1
1...[?]11... la machine est sortie de notre séquence initiale 00 par la gauche et dans l'état 1.
On peut donc "compiler" ce programme en lui rajoutant une "méta
instruction" :
si la tête est sur le premier symbole d'une séquence
00 dans l'état 1, alors remplacer la séquence par "11" et
positionner la tête à gauche de la séquence dans l'état
1, on aura "sauté" 3 étapes
Ce qu'on peut noter : 1G00 -> 1G11:3, qui est une "compilation" partielle du programme. L'important est que l'on pourra "compiler" une suite d'actions de la MdT si, entre l'entrée de la tête (ici à gauche) d'une séquence et sa sortie par la gauche ou la droite des cases définies par la séquence, la tête reste sur les cases de la séquence.
Dans le cas de machines plus compliquées, il sera possible d'avoir
des instructions compilées du genre :
"Si la tête est à gauche de la séquence formée
de n fois "100101" et dans l'état 3, alors elle va se retrouver au bout
de n*n*2+2n+1 itérations à droite de 2n fois la séquence
110 et dans l'état 9", en étant resté entre temps
sur les 6n cases de la séquence.
La compilation a permis de simuler la MdT en gagnant un sacré nombres de pas. On voit que la séquence finale 110110110... a la même longueur que la séquence initiale 100101100101...
On aura besoin d'un langage de description du ruban, qui permette
de décrire une partie du ruban en terme de choses comme "p fois
la séquence 1010", qui est d'ailleurs ici identique à "2p
fois la séquence 10". On voit ici la difficulté due à
certaines ambiguïtés :
pour décrire 10010010010,
faut il dire "10 puis 3 fois 010", ou "1, puis 3 fois 001, puis 0"
, ou encore "3 fois 100 puis 10" ?
Notre langage doit théoriquement éviter ce genre d'ambiguïtés,
mais en fait rien n'empêche de compiler les trois descriptions !
La machine de Turing à accélération
L'idée de la machine de Turing à accélération que je propose est de réaliser cette compilation au fil de l'eau (just in time) : la machine va apprendre son propre fonctionnement tout en s'exécutant... de plus en plus vite.Concrètement, à chaque fois que la machine exécute une instruction (compilée ou non), elle va "regarder ce qui s'est passé" lors des deux (ou même n) instructions précédentes : la tête était elle à gauche ou à droite d'une séquence (définissant une suite de cases), et se retrouve-t-elle après exécution des n instructions juste à gauche ou à droite de cette même suite de cases, sans en être sorti entre temps ? si oui, on peut générer une nouvelle instruction compilée.
Les détails de l'implémentation de cette idée "simple" sont compliqués. Avant de se plonger dans les délices de ces arcanes, faisons quelques remarques qui montreront le but de mon travail ... et son intérêt (j'espère !)
Première remarque
Tout d'abord il faut bien voir que l'on a deux processus, que l'on peut exécuter séquentiellement mais aussi en parallèle :- Un processus qui exécute la MdT
- Un processus qui compile ne nouvelles instructions en analysant ce que fait le premier.
Si aucune description ne matche, alors on exécute "bêtement" un pas de la MdT telle que définie à l'origine. Notons que ce processus est parfois moins efficace que la MdT "bête" initiale car ont perd du temps a essayer d'en gagner en matchant des descriptions.Le second processus peut être décomposé en deux parties,
- l'"analyseur", qui doit conserver l'historique (au moins partiel) de ce qui s'est passé et se poser la question "suis-je à gauche ou a droite d'une séquence dont la tête n'est pas sortie entre temps" ?
- Le "compilateur", qui à partie des informations fournies par l'analyseur doit créer une nouvelle instruction compilée qui pourra alors être plus tard être utilisé pa r le processus d'exécution si la même situation se représente (ce qui est assez fréquent d'ailleurs avec les MdT "qui font quelque chose d'utile").
Seconde remarque : limite théorique de l'intelligence
Ces deux processus sont parfaitement déterministes et on peut théoriquement les simuler sur une machine de Turing Universelle. La question fondamentale est :Cette machine de Turing universelle incorporant le mécanisme d'accélération que je propose est-il plus éfficace que la MdT universelle "standard" ?
Traditionnellement en théorie de la complexité, on caractérise un problème donné par la taille des données : par exemple si le problème est de trouver le plus court chemin passant par toutes les villes d'une liste donnée, la taille du problème est caractérisée par le nombre de villes. On dit qu'un problème est "de complexité f", où f est une fonction croissante R+ -> R+, si pour une taille suffisamment grande du problème, aucune machine de Turing (ou aucun ordinateur) ne peux résoudre le problème en un temps inférieur à f(la taille). Les spécialistes de la théorie de la complexité ont ainsi trouvé des problèmes intrinsèquement polynomiaux (on peut trouver un algorithme qui résolve le pb en un temps polynomial vis a vis de sa taille, mais pas en un temps linéaire), on encore intrinsèquement exponentiels : ces derniers problèmes sont d'ailleurs dits "difficiles".
Par exemple supposons qu'on écrive une MdT "F" qui soit capable de factoriser tout entier n préalablement écrit sur le ruban : la taille du problème est le nombre de chiffres de n
On simule F sur une MdT universelle "standard" MU, et sur une MdT universelle "à accélération" MUA : laquelle est la plus rapide ? Que dire si MUA est capable de factoriser un nombre n en en temps logarithmique par rapport au nombre de chiffres de n, alors que les meilleurs algorithmes ont un temps en n ? Pire : une fonction non calculable "classiquement" ne pourrait-elle pas devenir calculable lorsqu'on utilise MUA ? Ce serait une révolution.. incalculable de notre point de vue sur la complexité et même la nature de l'intelligence !
La première approche de ce problème est de dire que MUA n'est jamais qu'une machine de Turing particulière, et que les concepts de la théorie de la complexité restent valables : un problème intrinsèquement exponentiel restera exponentiel lorsqu'on cherchera à le résoudre.
Mais cette réponse pose à son tour un problème si on l'admet comme axiome :
En effet ils est indéniable que MUA, de part sa capacité d'auto-apprentissage, aura un temps d'exécution (mesuré en nombres d'instructions compilées exécutées) beaucoup plus rapide que la simple MdT qu'elle simule. Il est a peu près certain qu'on pourra trouver des exemples de problèmes exponentiels solvables en un temps polynomial avec MuA (si l'on mesure le temps en nombre d'instructions compilées exécutées). En d'autre terme, sur mon PC je simule la MdT M qui correspond à ce difficile problème exponentiel, et je simule aussi la MdT "à accélération" qui émule M ; si malgré tout, "au final", on n'est pas plus rapide, où a-t-on perdu du temps ? Est-ce dans le processus de compilation, dans le processus d'exécution , ou les deux ?
Quelle que soit la réponse, on aurait une limite fondamentale à l'intérêt de l'apprentissage :
Aucun processus d'apprentissage par auto-observation ne sera suffisamment efficace pour abaisser le degré de complexité d'un problème quelconque.
Ceci signifie que par exemple il ne sert à rien d'accumuler des
connaissance en mathématiques, un problème de complexité
nlog(n) ne pourra jamais être résolu en un temps n, même
avec une MUA.
Je trouve cela difficile à croire, et même impossible
!
J'en ai en effet un contre exemple : le problème très simple de l'élévation au carré d'un nombre n. Il est bien connu que ce problème est de complexité log(n) : en moyenne, pour élever au carré le nombre binaire 101001001001, j'aurai exécuté un multiple (constant) de 12 opérations élémentaires (sur une machine disposant d'un processeur à 1 bit !), car n a 12 bits. Or il est possible de compiler une machine de Turing qui effectue le résultat en une seule opération :
On suppose un codage unaire du nombre n, c'est à dire
on l'écrit comme une suite de n "1" successifs.
Alors soit la méta instruction compilée :
si la bande contient n "1" successifs, suivis de zéros, alors
remplacer la séquence par n2 "1" successifs.
Je prétend que la machine de Turing à accélération mettra un nombre d'étapes fini et constant pour trouver cette méta instruction : il suffit ensuite de l'exécuter en une étape.
Vous allez dire que c'est de la triche : je reporte la difficulté du problème sur le processus d'exécution, qui contient la multiplication en "built-in"). Peux être, mais le fait est que lorsque l'écrit la MdT S qui réalise l'élévation au carré, puis que j'exécute sur mon ordinateur cette MdT, puis la MdTA qui émule S, la seconde ira bien plus vite (pour des grand nombres). Pourtant mon ordinateur peut être émule par une machine de Turing et l'on trouvera le même rapport de vitesse !
L'axiome de départ "l'auto observation ne sert à rien" me parait donc faux par contradiction.
On se trouve donc devant une régression infinie : s'il est possible d'abaisser la complexité d'un problème en s'auto-analysant pendant la résolution dudit problème, alors tous les problèmes ont, in fine, une complexité constante qui est le temps que mettra la MUA à trouver la "bonne" instruction compilée qui résout tout le problème en une seule étape. Faut-il jeter la théorie de la complexité aux orties ?
L'intérêt de cette spéculation est que l'esprit
humain est comme chacun sait, un processus qui s'auto analyse...
La réalisation d'une MUA
Nous auront besoin de fonctions de filtrage et de réécriture, et donc il sera utile d'envisage rune implémentation en prolog ou en lisp.Commençons par le langage de description de séquences.
Page en chantier
Désolé ! Sois patient...
> La suite : La conjecture P-NP
Jeu de briques
Snake
Pacman
Bubble