Machine de Turing - préliminaires en C
Dans la maquette, nous avons vu que coder une machine de turing universelle ne semble pas être un exploit en tant que tel. Observons maintenant les difficultés inhérentes au C.
1) il n'y a pas de type liste préfabriqué pour les rubans. Prolog manipule ce genre d'objet nativement, pas C.
2) le stockages des états: comment exprimer en C que la transition associée à un état est possible? en prolog il suffisait de déclarer le prédicat vrai, en C il n'y a pas de tel moyen.
3) le moteur de déduction: en prolog on avait une récursion qui formait le moteur de la machine. En C, il semble assez peut malin de procéder de la même manière.
1 LES RUBANS
Il y a le choix. Dans la maquette on utilise deux listes, une à droite, l'autre a gauche. En C on peut refaire la même chose, c'est a dire détacher la tête d'une liste (pas d'un roi) pour la poser sur l'autre.
Sinon on peu faire une seule liste, mais avec un double chainage. Avec l'astuce du XOR on peut même faire une économie de 1/3 sur la place occupée par les pointeurs construisant le chaînage double.
J'ai pas encore décidé.
2 DÉCLARATION DES ÉTATS
Bon, c'est plus simple.
Il va falloir déclarer et stocker les états. Il faut aussi un accès rapide parce que ces données seront accédées régulièrement. Le plus rapide c'est un tableau, organisé en table de hachage.
3 EXECUTE
Tout viens à point à qui vient attendre.
1) il n'y a pas de type liste préfabriqué pour les rubans. Prolog manipule ce genre d'objet nativement, pas C.
2) le stockages des états: comment exprimer en C que la transition associée à un état est possible? en prolog il suffisait de déclarer le prédicat vrai, en C il n'y a pas de tel moyen.
3) le moteur de déduction: en prolog on avait une récursion qui formait le moteur de la machine. En C, il semble assez peut malin de procéder de la même manière.
1 LES RUBANS
Il y a le choix. Dans la maquette on utilise deux listes, une à droite, l'autre a gauche. En C on peut refaire la même chose, c'est a dire détacher la tête d'une liste (pas d'un roi) pour la poser sur l'autre.
Sinon on peu faire une seule liste, mais avec un double chainage. Avec l'astuce du XOR on peut même faire une économie de 1/3 sur la place occupée par les pointeurs construisant le chaînage double.
J'ai pas encore décidé.
2 DÉCLARATION DES ÉTATS
Bon, c'est plus simple.
Il va falloir déclarer et stocker les états. Il faut aussi un accès rapide parce que ces données seront accédées régulièrement. Le plus rapide c'est un tableau, organisé en table de hachage.
3 EXECUTE
Tout viens à point à qui vient attendre.