H. Td, Calculabilité 2 (´ enumérations et indécidabilité)

H. Exercice, 1 On considère l'ensemble N * des mots finis de nombres naturels. Notez que N * est en correspondance bijective avec k?0 N k

?. =. Soit, On peuténumérerpeuténumérer lesélémentsleséléments de ? * comme suit : , a, b

*. Exercice, Montrez qu'un langage est semi-décidable si et seulement si il est le domaine de définition d'une fonction partielle récursive

. On-dit-qu-'un-langage-l-?-?-*, est récursivementrécursivementénumérable s'il est l'image d'une fonction partielle récursive Montrez qu'un langage L est récursivementrécursivementénumérable si et seulement si il est semi-décidable. Suggestion : Soit M une MdT et w 0 , w 1 , w 2 , . . . une suite d'entrées. On peut simuler M sur w 0 pour 0 pas, sur w 0 pour 1 pas, sur w 1 pour 0 pas

H. Exercice, 5 Montrez ou invalidez les assertions suivantes : 1. Il y a une MdT qui accepte les mots sur l'alphabet {0, pp.1-1

H. Exercice, 6 Montrez ou donnez un contre-exemple aux assertions suivantes : 1. L'ensemble des (codages de) MdT qui terminent sur le mot vide est décidable

*. Exercice, OnécritOnécrit X > 1 Y si Y est obtenu de X en remplaçant unélémentunélément de X par un multi-ensemble d'´ eléments strictement plus petits

L. Exercice, 4 Soit N * les mots finis de nombres naturels. Montrez la terminaison du système : u(i + 1)v ? iviui pour u

N. Exercice, 1 ´ Ecrire un programme qui traduit unprobì eme de Sudoku en une formule CNF sous le format DIMACS. Ce programme prend comme entrée un fichier sous la forme définie dans la partie précédente et doitécriredoitécrire le

N. Exercice, 2 ´ Ecrire, une fonction qui transforme une affectation qui satisfait la formule en solution du Sudoku et l'affiche