L3 Informatique Calculabilit´e 18 septembre 2014 TD2 Charg´ ee de TD : Marie van den Bogaard [email protected] http://www.lsv.ens-cachan.fr/~mvdb/calculabilite Exercice 1 (Clˆ oture des langages r´ ecursifs) Montrer que la classe des langages r´ecursifs est close par les op´erations bool´eennes : intersection, union, compl´ementaire. Exercice 2 (Fonctions calculables et langages r´ ecursivement ´ enum´ erables) Soit f une fonction calculable. Montrer que l’image de f est un langage r´ecursivement ´enum´erable. Exercice 3 (Clˆ oture des langages r´ ecursivement ´ enum´ erables) Montrer que la classe des langages r´ecursivement ´enum´erables est close par union et intersection. Exercice 4 (Caract´ erisation des langages r´ ecursivement ´ enum´ erables) Montrer que L est un langage r´ecursivement ´enum´erable si et seulement s’il existe une machine de Turing M a` deux rubans et un ´etat distingu´e qe de M tels que : q0 , (, $), (, $) `∗M qe , (, $w0 ), (, $w) ssi w ∈ L Exercice 5 (Image de langages r´ ecursivement ´ enum´ erables) Montrer que, si f est calculable et L est r´ecursivement ´enum´erable, alors f (L) est r´ecursivement ´enum´erable. Exercice 6 (Fonctions calculables et langages r´ ecursifs) Donner une fonction calculable dont l’image n’est pas r´ecursive. 1
© Copyright 2024 ExpyDoc
