Machine de Turing

Je ne sais pas si c'est plus de l'info ou des maths, mais comme je l'avais prévenu, j'ai quelques questions sur les machines de Turing (MT)...

Enumération de Kleene...
1) Ca veut dire quoi "une MT est codée par un mot de Z où Z est un alphabet" ?
2) Ca veut dire quoi "un ruban est codé par un mot de Z où Z est un alphabet" ?

D'autres questions viendront au fur et à mesure de la lecture de mon cours.

Théorème de la halte
3) Je n'ai rien trouvé sur ce théorème sur Google à part ça : http://www.quadibloc.com/math/undint.htm !
Si tu vois ce que c'est, (Duche ou les autres !), tu pourrais m'expliquer la démonstration ? J'ai du mal avec les notations du cours...

Alors un alphabet est un ensemble fini ou dénombrable de symboles prédéfinis.
Quand on dit que x est un mot de Z c'est que c'est une suite finie de symboles dans Z.

Par exemple, prenons Z = { 'a' , '2' , '%' , '@' , 'M'}
%%%%%%%%%%%%%%
M2M2M2
MaM%M@M
22222222@2
sont des mots de Z

"un ruban est codé par un mot de Z où Z est un alphabet"
-> un ruban sur lequel sont imprimés une successions de symboles.

"une MT est codée par un mot de Z où Z est un alphabet"
-> Je suis pas trop sur, il me faudrait un contexte.
Mais je dirais que pour connaitre les données d'une machine de Turing, il faut les encoder, ce qui peut être fait par une successions de symboles dans un alphabet donné (par exemple du français et notre alphabet). La MT peut donc être décrite ou 'codée' par une succession de symboles.

Remarque intéressante: si une machine de turing peut se résumer à une suite finie de symboles sur un ruban, elle peut être lue par une autre machine de turing, elle même codée sur un ruban, etc... flippant non ?

Pour le problème de la halte, je suis un peu malade et je t'avoue que j'ai pas envie de lire en anglais maintenant. est-ce bien le problème qui dit que l'ont ne peut écrire un programme capable de décider si tout programme s'arrête ou non ?

C'est bon, j'ai mieux compris l'idée avec tes explications !

Duche a écrit:Remarque intéressante: si une machine de turing peut se résumer à une suite finie de symboles sur un ruban, elle peut être lue par une autre machine de turing, elle même codée sur un ruban, etc... flippant non ?

En gros, il faut construire un alphabet qui contient l'alphabet d'origine plus des caractères désignant les transitions ? La nouvlle MT serait alors une concaténation de transitions ?

Pour le problème de la halte voici l'énoncé :
il n'existe pas de MT T(x,y) tel que
* T s'arrête sur toute entrée
* T s'arrête avec un 1 sur son ruban si Ph_x(y) s'arrête
* T s'arrête avec un 0 sur son ruban si Ph_x(y) ne s'arrête pas.

(Bon rétablissement )

Oui c'est donc bien le problème d'arrêt auquel je pensais.
La démo est cool !

Duche a écrit:La démo est cool !

C'est justement ça que je veux xomprendre ! lol

Bon pour la démonstration du problème de la halte, c'est pas très grave. Il est aussi appelé problème de l'arrêt. Mais j'ai d'autres questions !

4) Montrer que le problème suivant est indécidable :
déterminer si un programme écrit en C s'arrête pour des valeurs fixées.

5) récursif et décidable sont tout à fait synonymes ou il y a une différence ?

J'ai essayé de refaire la démo tout seul, mais j'avais un peu de mal (pas bien réveillé encore)
J'ai trouvé ça pour toi
http://www.juniata.edu/faculty/rhodes/intro/theory2.htm

OK merci, je vais regarder ça de plus près.

T'as une idée pour la 4° question ?

Oui ben c'est ça la 4ème question ^^

Ah ben oui en effet, je pensais que c'était la démonstration du problème de la halte ^^

Le lien est bien explicite et il y a peu de notations ! Merci !