Machine de Turing - maquette

Bonjour,


INTRODUCTION
J'ai en projet pour occuper mes soirées douces et très très longues d'écrire une petite machine de Turing en langage C. A quoi ça sert? à presque rien. Le seul truc c'est qu'avec une machine de Turing on peut réaliser un castor affairé (Busy Beaver) qui est un algorithme qui permet de compter pendant très longtemps et puis ça s'arrêter tout seul, sans planter. Je trouve ça fascinant...

Bref...
Le but est de fournir un machin qui, s'il n'a aucun intérêt intrinsèque (pour le commun des mortels), est quand même un défit au niveau calculatoire. attendez je retrouve les chiffres...  un castor affairé 1 ruban et 6 états permettrait de compter jusqu'à l'entier 95.524.079 en partant de 'rien' avec un nombre de pas de calculs de 8.690.333.381.690.951. Et encore on n'est pas sur que le candidat en question soit le plus performant.

Non il ne s'agit pas de faire une simple boucle qui s'auto-incrémente (avec WHILE ou FOR). Parce que comment on s'arrête alors? Comment on choisi le plus grand entier? Dans un castor affairé on ne code en aucune manière (ou alors très inconsciemment ) le nombre sur lequel on s'arrête.

Une machine de Turing ce n'est pas obligatoirement pour faire des castors affairés. C'est aussi le modèle mathématique d'un ordinateur. Un état de la machine équivaut vite fait à une case mémoire de l'ordinateur, alors qu'une transition est à peu près un pas de programme, c'est à dire notre hobby. L'ordinateur d'aujourd'hui n'est pas tout à fait basé sur le modèle de Turing, qui en bon mathématicien cherchait (et à trouvé) une machine universelle qui serait capable de faire tout marcher en théorie, mais sur le modèle de Von Neumann  un peu plus pragmatique... gnagnagna... rendez vous sur  Wikipédia.


MACHINE DE TURING UN RUBAN
A propos de l'implémentation, on observe que le ruban bi-infini de la machine est matérialisé par deux listes, une pour la partie droite, l'autre pour la partie gauche. En observant fonctionner ma machine vous verrez que les têtes de listes sont toujours les cellules à coté de la tête de lecture et que l'infini est dans les deux cas en queue de liste. J'en ai fait exprès.. les informaticiens sont, je pense, des gens astucieux.

Sans plus tarder, voila ma maquette en PROLOG d'une machine de turing. Prolog est langage script d'origine lointenement française avec une parenté avec un langage à liste comme LISP, avec en moins les parenthèses et en plus la résolution logique et l'unification. Je vais encore perdre des lecteurs au profit de Wikipédia. Ici c'est du swi-prolog. 

Au fait, i'm sorry for people who don't speak a word in french. My code is written with french name and i know it's bad.

/*
 * Prédicat d'appel de la machine de Turing
 * on note que Etat est le nom de l'état initial voulu (logiquement q0)
 * RG est le ruban à gauche de la tête de lecture dans le sens habituel de lecture.
 * RD est le ruban à droite de la tête de lecture dans le sens habituel de lecture. 
 * Resultat est le ruban tel que la machine le laisse lorsqu'elle s'arrête (peut être passé à _)
 *
 * usage : Etat Initial, 
 * [ 1er caractère .. caractère suivant ] , 
 * caractère sous la tête de lecture , 
 * [ caractère suivant .. dernier caractère]'),
 * X 
 */
machineUnRuban( Etat, RG, TeteLecture, RD, Resultat) :- 
 transition(Etat, _, _, _, _),!,
 write('etat initial < '), write(Etat), write(' > '), nl,
 write('debut du ruban '), write(RG), nl, 
 write('tete lecture < '), write(TeteLecture), write(' > '), nl, 
 write('suite du ruban '), write(RG),nl,
 renverser([blanc|RG], GR),
 executer(Etat, GR, [TeteLecture|RD], Resultat).

/*
 * la vrai machine.
 * le ruban gauche RG est renversé comme il me sied.
 */
executer( Etat,RG,[Lecture|RD], Resultat) :-
 % write(RG), write(' < '), write(Lecture), write(' > '), write(RD), nl,
 transition( Etat, EtatSuivant, Lecture, Ecriture, Deplacement),
 ecrire(Ecriture, [Lecture|RD], NouveauRD),
 deplacer( Deplacement, RG, NouveauRD, RubanGauche, RubanDroit),
 executer( EtatSuivant, RubanGauche,RubanDroit, Resultat).
 

executer( Etat, RG, RD, Ruban) :-
 final(Etat),
 unifierRuban( RG, RD, Ruban).


/* 
 * deplacer le ruban. 
 * Les coupures pour enlever les points de choix sur ses affirmations, 
 * normalement il ne devrai pas y avoir de point choix dans une bonne machine de Turing.
 */

deplacer( d, [blanc], [Suivant|[]], [Suivant], [blanc]) :- !.
deplacer( d, RubanG, [Suivant|[]], [Suivant|RubanG], [blanc]) :-!.
deplacer( d, [blanc], [Suivant|RubanD], [Suivant], RubanD) :- !.
deplacer( d, RubanG, [Suivant|RubanD], [Suivant|RubanG], RubanD):-!. 

deplacer( g, [Precedant|[]], [blanc], [blanc], [Precedant]):-!.
deplacer( g, [Precedant|[]], RubanD, [blanc], [Precedant|RubanD]):-!. 
deplacer( g, [Precedant|RubanG], [blanc], RubanG, [Precedant]):-!. 
deplacer( g, [Precedant|RubanG], RubanD, RubanG, [Precedant|RubanD]):-!. 

deplacer( s, RubanG, RubanD, RubanG, RubanD).


/*
 * ecrire sur le ruban
 */
ecrire(Lettre, [_|Liste], [Lettre |Liste]).


/*
 * petite primitives
 */

renverser( [], []).

renverser([X|Y],R):-renverser(Y,L), append(L,[X],R).

/*
 * unifier le ruban gauche et droite dans une seule liste.
 */
unifierRuban( [], Ruban, Ruban).
unifierRuban( [Precedant|RG], RD, Resultat) :-
 unifierRuban( RG, [Precedant|RD], Resultat). 

/**/

TRANSITIONS
Voilà maintenant la définition des transitions pour réaliser le fameux castor à 6 états et 1 ruban. L'état final ne compte pas comme un état.

/*
castor à 6 "pattes"
transition (étatdepart, étatcible, lu sur le ruban, écrit sur le ruban, déplacement du ruban)
*/

transition( castor6A, castor6A, 1, 1, d).
transition( castor6A, castor6B, blanc, 1, d).
transition( castor6B, castor6B, 1, 1, g).
transition( castor6B, castor6C, blanc, 1, g).
transition( castor6C, castor6D, 1, 1, g).
transition( castor6C, castor6F, blanc, blanc, d).
transition( castor6D, castor6E, 1, blanc, g).
transition( castor6D, castor6A, blanc, 1, d).
transition( castor6E, castor6F, 1, 1,g).
transition( castor6E, h, blanc,1, g).
transition( castor6F, castor6C, 1, blanc, g).
transition( castor6F, castor6A, blanc,blanc,g).

/**/

On notera que les états sont tous nommés, avec des noms "castor6" pour désigner le nom de la machine et une lettre pour désigner l'état. En effet dans le même script j'ai défini un castor à 3 pattes:

/*
castor à 3 "pattes"
transition (étatdepart, étatcible, lu sur le ruban, écrit sur le ruban, déplacement du ruban)
*/

transition( castor3A, castor3C, 1, 1, g).
transition( castor3A, castor3B, blanc, 1, d).
transition( castor3B, castor3B, 1, 1, d).
transition( castor3B, castor3A, blanc, 1, g).
transition( castor3C, castor3B, blanc, 1, g).
transition( castor3C, h, 1, 1, d).

/**/ 

Je vous laisse essayer...


CONCLUSION
Bon Prolog c'est bien, mais on voit que ce n'est pas fait pour réaliser des prouesses de programmation et que Prolog est incapable d'exécuter un prédicat qui génère une récursion si longue. Par contre c'est trivial pour utiliser des listes... bref il nous faut du C qui lui n'est pas fort pour les listes...

les questions a se poser sont :
 * comment faire pour la pile d'appel -> reconvertir en boucle.
 * comment gérer la mémoire pour tout écrire dans la mémoire de not' petite machine?
 * comment faire pour que ça aille bien vite?

mise à jour:

Ces techniques permettent de se débarrasser de la contrainte de profondeur de boucle...

for( Flag, Variable, From, To, Step, Do ) :-
 flag(Flag, _, From),
 repeat,
 flag(Flag, Courant, Courant),
 Courant = Variable,
 Do,
 Suivant is Courant + Step,
 flag(Flag, Courant, Suivant),
 Courant = To,!. 

pour le do..while on pourrait mieux faire, cette implémentation n'est pas super, je n'ai pas le temps de creuser. Ca s'appelle réinventer le findall...

dowhile(Action, Condition) :- 
 repeat,
 Action,
 Condition,
 (
 retract(dowhile(Condition)) , write('fini') , !
 );(
 (
 dowhile(X) , X \= Condition , fail
 );(
 assert(dowhile(Condition)) , fail
 )
 ).

On peut faire largement mieux avec setarg spécifique à prolog... d'utilisation déconseillée parce qu'on perd les propriétés de logique.