Machine de Turing - préliminaires en C

Publié le par JJ

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.

Commenter cet article

maurille 14/05/2007 10:33

Salut,je suis justement très interresser par le projet ,mais ça fait un moment que je surveille l'ariticle ,sans qu'il ne bouge...Il y aurai t-il un moyen d'avoir la suite ...Notament un exemple de code stp (déclaration puis stockage des etats,les transitions...).Merci.
Serait-il possible réellement de faire des trucs comme des calculs (addition ) binaire avec une machine de turing? J'ai lu un peu partout
qu'en théorie elle peut tout faire ou presque ,tel un ordinateur ... 

JJ 12/03/2008 22:49

bonjour,c'est vrai que je n'ai pas bcp avancé sur ce projet... probablement je ne publirai jamais rien sur ce site sauf un lien qui demande d'aller voir peperillon.free.fr.Est ce qu'on peut faire des calculs avec la machine de turing? oui. en fait on fait exactement comme si on compte avec les doits. 2 doigts ouverts et 1 doigt ouvert font 3 doigts ouverts. c'est comme ça qu'on reconnait le résultat. la machine que j'ai codé c'est une machine de base à 2 états. c'est a dire que pour faire une somme on met une quantité de doigts d'un coté , une autre de l'autre. une fois qu'on a déplacé une des deux quantités pour qu'il n'y ai plus aucun symbole entre les deux quantités alors on peut arreter la machine: on a terminé la somme: la fusion de deux quantité en base 1.il est possible de faire une machine qui fait des additions, des soustractions et même qui corrige les fautes d'orthographe. A partir du moment ou on peut faire un algorithme alors c'est très simple. On n'a le choix que du language. On peut choisir de représenter son algo par un réseau d'état et c'est le dessin de la machine. On peut choisir d'impémenter des instruction très évoluées. La seule différence c'est l'efficacité du travail de l'homme.Historiquement la machine de Turing est l'ancetre de l'ordinateur. Si ma mémoire est exacte c'est Turing qui a commencé: en tant que mathématicien il a créé une "machine" (le mot algorythme n'existait pas encore) très généraliste. Après sa mort, ses travaux ont été repris par un Américain(?) Von Neuman qui s'est appercu que l'approche machine généraliste n'était pas assez performante alors il a créé le modèle de l'ordinateur actuel avec des instructions plus efficaces (par exemple l'opération "ne rien faire" c'est un NOP alors qu'avec turing il faut aller dans un état spécialement prévu passer d'un état à l'autre et revenir là ou on était (enfin juste après).Turing était un géni. Si sa machine avait été utilisée comme modèle de l'ordinateur, probablement que les ordinateurs serait infaillible. Probablement aussi que personne n'arriverai à écrire un programme.Pour pousser les détails, la théorie de Turing est indispensable pour faire des compilateurs et tout ce qui fait des analyses de textes (et donc le correcteur d'orthographe) parce que cette théorie donne une forme acceptable au travail à faire. Personne ne dit que c'est simple de faire un correcteur d'orthographe.