Parent directory
acceder au document
/*
* Pierre-Emmanuel Périllon
* free for non commercial use.
* date december 2006
*/

/*******************************************************************************/
/*********************** TURING 'S MACHINE in prolog ***************************/
/*******************************************************************************/
/*
* 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).

/**/

/*******************************************************************************/
/*
* castor à 6 "pattes" (busy beaver)
* transition (étatdepart, étatcible, lu sur le ruban, écrit sur le ruban, déplacement du ruban)
* (this is unusable because of the amout of memory needed)
*/

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).

/*******************************************************************************/

/*
* 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).

/**/
acceder au document