Journal d'un terrien

Web log de Serge Boisse

On line depuis 1992 !

Recherche personnalisée

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)
Cette machine écrit trois "1" sur le ruban, puis s'arrête.
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 : Le premier processus commence par regarder la liste des descriptions de ruban correspondant aux instructions déjà compilées qui ont pour état de départ l'état courant de la tête, et tente de faire un filtrage (pattern matching) de la situation réelle du ruban avec cette description : si les deux descriptions "matchent" , alors on peut exécuter l'instruction compilée et gagner du temps. Pour plus d'efficacité, lorsque plusieurs descriptions "matchent", on prendra celle qui décrit la plus longue partie du ruban actuel.
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,

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

Journal d'un terrien

Commentaires (5) :

Page : [1] 

Duna
Le 02/12/2015 à 12h14
J'étais emballé par le titre, mais comme le dit jj, il y a une grosse erreur de logique. "Compiler" une machine de Turing tel que vous l'entendez revient à changer sa table de transitions, mais aussi (et c'est bien plus important !) le nombre d'états.

Un problème non calculable sur une machine à n états eut devenir calculable sur une "machine à accélération" à n états. Mais cette dernière est équivalente à une machine à m états avec m>n. Et sur cette machine à accélération, il sera toujours impossible de calculer un problème incalculable avec m états.



Pour répondre à la question "si malgré tout, "au final", on n'est pas plus rapide, où a-t-on perdu du temps ?" :

Pour la partie théorique, dans l'étape d'exécution. Écrire 2 fois la lettre '1' sur le ruban est de longueur 2, même si c'est une seule transition qui s'en charge. Cette erreur conceptuelle est la même que si je définis une fonction ack qui calcule la fonction d'Ackermann, puis dis je calcule en 1 étape ack(5,4) !

En pratique, la perte de temps se ferait aussi au moment de la compilation et de l'observation.
rem
Le 10/06/2015 à 21h44
on peut imaginer aussi que l'auto analyseur analyse des séquence de ces analyses compilés, en extrait des stabilités qu'il code comme des suite de compilation qui s'effectue d'un coup quand certaines conditions sont donné, et cela à l'infini avec des analyse d'analyse etc... il économise de la mémoire et puis il peut découvrir des simplifications de ses empilements de block compilés, cela me semble possible mais indécidable c'est à dire qu'on ne pourra pas savoir si un pb est simplifiable ainsi à l'avance (ça sera variable d'1 pb à l'autre), de plus un nouveau critère entre en compte c'est celui de la complexité de l'outil d'analyse lui même, et il me semble que cet outil est "incommensurable" je veux dire par cela qu'il n'existe peut être pas de critères permettant de juger si on est pas passé à coté de combinaison complexe de séquences d'analyses imbriqués qui simplifie véritablement le pb, peut on mesurer la commensurabilité de l'intelligence avec l'intelligence!!!!
Serge Boisse
Le 01/09/2011 à 19h00
pour jj:

Qui a dit que l'auto observation était constante ? pas moi !

Je vais essayer de résumer mon idée : on échange de la vitesse contre de la mémoire, et plus précisément, je pense que

NP = EXPSPACE

ce qui implique que P = NP, mais avec cette condition qu'il faut accepter de consommer exponentiellement de la mémoire pour exécuter des programmes NP-complets...

La découverte récente que IP = PSPACE va dans ce sens... Pour l'instant personne n'a pu trancher cette question, donc pourquoi pas ?
jj
Le 26/08/2011 à 19h01
Bonjour

il y a une erreur logique. penser que le phénomène "d'auto observation" est constant en fonction de l'expérience de la machine de turing est une anerie sans nom.



Moi aussi je sais faire une multiplication en une seule operation. J'utilise une rainbow table.



et un petit moins un pour le ptit applet JS qui perturbe la lecture.
Tiboulen
Le 03/06/2011 à 10h46
Votre idée concernant une machine de Turing à accélération est interessante et parfaitement correcte; Cela se rapporte à un problème de pure géométrie logarithmique. Tous les problèmes sont approchables en temps logarithmique, mais avec une limite de précision. L'algorithme à mettre en place est dans la lignée de votre idée. Je vous ferais parvenir un ouvrage si j'ai vos coordonnées. Les miennes : mw@tiboulen.com


Ajouter un commentaire (pas besoin de s'enregistrer)

Pseudo :
Message :


image de protection
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !
Ah oui : le html genre <br>, <a href=...>, <b>b etc. ne fonctionne pas dans les commentaires. C'est voulu.
< Retour en haut de la page