1. IF --> GH Bonjour, j'ai été voir 4 versions différentes pour la preuve comme quoi le language Etm n,est pas décidable Aka ( | M est MT et L(M) = O) Je bloque toujours sur un élément de la preuve qui ne semble pas faire de sense... Dans tous les exemples on batit une MT (M1) ou .. dans nos notes de cours c'était M' qui elle va prendre un x et une . M1 "accepte" Sigma* si w fait parti de L(M) et "rejette" en retournant O sinon. Cette construction me semble illégale. On l'utilise pour l'envoyer a la suite de la preuve mais... est-ce qu'elle ne décide pas de Lu? Car si je peux simuler w sur M et en déduire Sigma* (et sinon donner un O), alors ca ressemble beaucoup a Lu. C'est comme ci on se servirait de Lu pour dire que Emt n'est pas possible car elle décide de Lu. Ce qui est un nonsense... Ca tourne en rond. Et je n'arrive pas a comprendre. J'ai essayer de comprendre dans Sipser et sur ce beau document http://www.cs.unb.ca/courses/cs2333/undec.pdf et je reste vraiment mélangée. J'ai trouver une autre preuve qui utilise le théorème de Rice et qui est plus simple. --- Une autre question est est-ce que REGmt est reconaissable? (dire si le language d'une MT est regulier) Je crois avoir écrit dans mes notes que ce n'est pas reconaissable. Je sais que ce n'est pas décidable en tout cas. 2. GH --> IF Non, on ne se sert pas de Lu comme cela. 3. GH --> IF Un peu plus de details: Isabelle Filiatreault wrote: > Bonjour, > j'ai été voir 4 versions différentes pour la preuve comme quoi le > language Etm n,est pas décidable > Aka ( | M est MT et L(M) = O) > > Je bloque toujours sur un élément de la preuve qui ne semble pas faire de sense... > > Dans tous les exemples on batit une MT (M1) ou .. dans nos notes de cours c'était M' > qui elle va prendre un x et une . M1 "accepte" Sigma* si w > fait parti de L(M) et "rejette" en retournant O sinon. Cette > construction me semble illégale. On l'utilise pour l'envoyer a la > suite de la preuve mais... est-ce qu'elle ne décide pas de Lu? Car > si je peux simuler w sur M et en déduire Sigma* (et sinon donner un > O), alors ca ressemble beaucoup a Lu. La GROSSE difference est celle-ci : dans la construction, on utilise un w et une MT M () DONNES, fixes, et on s'en sert pour decider si un autre mot (x) est accepte par M1. Lu n'est pas decidable par ce que pour le decider, l'on devrait pouvoir dire pour TOUTE paire (M,w) si est dans le langage (Lu) ou pas. Si c'etait possible, la machine qui decide pourrait, a priori, decider sans jamais faire tourner M sur w (par exemple, quand j'ensaignait FORTRAN, je savais dire aux etudiants que leur programme bouclait sans l'executer). > > C'est comme ci on se servirait de Lu pour dire que Emt n'est pas > possible car elle décide de Lu. Ce qui est un nonsense... Ca tourne > en rond. Et je n'arrive pas a comprendre. > J'ai essayer de comprendre dans Sipser et sur ce beau document > http://www.cs.unb.ca/courses/cs2333/undec.pdf et je reste vraiment > mélangée. J'ai trouver une autre preuve qui utilise le théorème de > Rice et qui est plus simple. > C'est plus simple a condition de comprendre Rice. On a d'ailleur fait la preuve de Etm afin de faciliter la comprehension de la preuve de Rice! > --- > Une autre question est est-ce que REGmt est reconaissable? (dire si > le language d'une MT est regulier) Je crois avoir écrit dans mes > notes que ce n'est pas reconaissable. Je sais que ce n'est pas > décidable en tout cas. 4. IF --> GH Oui ca aide beaucoup! Si vous ditez qu'on exécute pas w sur M pour Lu 5. GH --> IF On execute M sur w pour montrer que Lu est RECONNAISSABLE; c'est le mieux que l'on sache faire/ Mais la difference principale est que Lu contient une infinite de mot tandis que la construction de M1 n'en utilise qu'un seul, la paire . On a plusieurs machines dans le feu: - l'hypothetique Me qui decide si le langage d'un machine donnee par son code est vide ou pas - la TM M() que nous appellons ici M1 mais qui, je veux souligner pas cette notation, depend d'une paire donnee - la machine donnee par son code , celle qui, avec son entree va faire a la fois l'entree pour Me et le paramatre de M() - Mu, une machine (nonexistante) qui decide Lu Ce qu l'on cherche a construire, c'est Mu, etant donne Me. Cette machine prendrait en entree un mot (paire) . Un fois fixe, la machine Me construit )>, qui est une machine qui A. sur l'entree x verifie si x=w (je suis ici les belles notes que vous avez citees, ma construction est un peu differente) et rejete si x<>w. Si x=w, elle simule M sur w. Son langage est donc soit vide, soit L(M), car elle n'acceptera que des mots de L(M) (voir plus bas - description B - pour la construction du cours). Donc son langage est vide si et seulement si w n'est pas dans L(M). On a donc des algos (MT) suivants Mu () sur l'entree appeler CON(,M(M<,w>)) faire tourner Me sur )> si Me dit OUI, retourner NON sinon retourner OUI CON(, )) sur l'entree retourner le code de M() et nous avons la descritpion de M(): au choix, la construction A ou B. B. sur l'entree x, la machine simule M sur w. Elle accepte x si et seulement si M accepte w. Donc L(M) et soit vide (w n'est pas accepte par M), soit Sigma* (w est dans L(M)). Donc L(M()) est vide si est seulement si M n'accepte pas w. Est-ce que cela aide? Et puis: est-ce que je peux faire passer aux autre notre echange? Jer pense qu'il y en qui en profiteraient... 6. IF --> GH C'est super, et oui, il pourrait être intéressant d'envoyer le courriel a tous, sans problèmes. Merci 7. GH --> IF L'important, ce n'est pas la rose mais si vous avez compris (et si vous n;avez pas compris la reference obscure, ce n'est pas grave, cela ne fait pas partie du cours). \end{document}