TD5 - Antonio E. Porreca · 2021. 1. 28. · Exercice 4.4 Donner un exemple de propriété non triviale • Il existe une machine de Turing qui accepte exactement tous les mots de

Calculabilité TD5Antonio E. Porreca

aeporreca.org/calculabilite

https://aeporreca.org/calculabilite

Examen session 1 2018–2019

Exercice 1 Notions de base

Exercice 1.1Compléter la phrase suivante : Un langage est récursif si et seulement si…

• …il existe une machine de Turing telle que

• accepte tous les mots

• rejette tous les mots

• s’arrête toujours

L

M

M w ∈ L

M w ∉ L

M

Exercice 1.2Compléter la phrase suivante : Un langage est récursivement énumérable si et seulement si…

• …il existe une machine de Turing telle que

• accepte tous les mots

• rejette tous les mots

• ⚠ On ne demande pas que s’arrête toujours : les mots sur lesquels ne s’arrête pas comptent aussi comme rejetés

L

M

M w ∈ L

M w ∉ L

MM

Exercice 1.3

Dans la définition des machines de Turing, pourquoi impose-t-on que ? (avec le symbole blanc, 

l’alphabet de ruban, et l’alphabet d’entrée)

• On utilise le symbole pour trouver la fin du mot d’entrée

• Si était un symbole d’entrée, on ne saurait pas où arrêter de lire le ruban d’entrée de la machine

B ∈ Γ ∖ Σ BΓ Σ

B

B

Exercice 1.4Soient et deux langages. Montrer que si et

est récursif, alors est récursif.

• Si est récursif, alors il existe une machine qui reconnaît et qui s’arrête toujours

• Si alors il existe une machine qui calcule la réduction tel que ssi (donc

s’arrête toujours)

L1 L2 L1 ≤Tm L2L2 L1

L2 M2L2

L1 ≤Tm L2 Mff : Σ⋆1 → Σ

⋆2 x ∈ L1 f(x) ∈ L2

Mf

Exercice 1.4• Voici une machine qui reconnaît et s’arrête toujours :

  simuler en obtenant ;  simuler et renvoyer le même résultat

• accepte ssi accepte

• accepte ssi ssi

• Donc reconnaît en s’arrêtant toujours, donc est récursif

M1 L1

M1(x) =Mf(x) f(x)M2(f(x))

M1 x M2 f(x)

M2 f(x) f(x) ∈ L2 x ∈ L1

M1 L1 L1

Exercice 1.5Parmi les deux affirmations suivantes, laquelle est correcte ? (a) Si est récursif, alors est récursivement énumérable. (b) Si est récursivement énumérable, alors est récursif.

• Si est récursif alors il existe une MT qui accepte les mots , rejette les mots et s’arrête toujours

• Donc, en particulier, c’est vrai que accepte les mots et rejette les mots , ce qui implique que est récursivement énumérable

• Donc (a) est la bonne réponse ; (b) n’est pas vrai en général, parce qu’on ne demande pas que la machine s’arrête toujours

L LL L

L Mw ∈ L w ∉ L

M w ∈ Lw ∉ L L

Exercice 1.6Donner un exemple de langage non récursivement énumérable, différent de

• (voir notes du CM3)

• Sinon, rappel : ssi et ; donc on peut prendre le complémentaire de n’importe quel langage qui soit mais pas

Lū = {⟨M⟩#w ∣ M n’accepte pas w}

Ld = {⟨M⟩ ∣ M n’accepte pas ⟨M⟩}

L ∈ R L ∈ RE L̄ ∈ RE

L RE R

Exercice 1.7

Donner si possible un exemple de langage non récursivement énumérable mais récursif

• C’est impossible, on a vu dans l’exercice 1.5 que chaque langage est aussi R RE

Exercice 1.8Donner si possible un exemple de langage non récursif mais récursivement énumérable

• , voici une machine qui le reconnaît :

simuler sur et renvoyer le même résultat

• Si accepte alors accepte

• Si rejette en s’arrêtant, alors rejette en s’arrêtant

• Si ne s’arrête pas sur , alors non plus sur

• reconnaît , qui est donc , mais il n’est pas (Corollaire 3, notes CM3)

Lu = {⟨M⟩#w ∣ M accepte w}

Mu(⟨M⟩#w) = M w

M w Mu ⟨M⟩#w

M w Mu ⟨M⟩#w

M w Mu ⟨M⟩#w

Mu Lu RE R

Exercice 2 Machine de Turing

Exercice 2.1Dessiner l’automate d’une machine de Turing qui reconnaît le langage suivant et qui s’arrête toujours :

L1 = {w1w2⋯wn ∈ {a, b}⋆ ∣ n ≥ 2 et n ≡ 0 mod 3 et wn−1 = a}

q0

qR

q1q2

a, a, Db, b, D

q′

B, B, G

q′ ′

a, a, Gb, b, G

a, a, G

a, a, Db, b, D

a, a, Db, b, D

B, B, DB, B, D

B, B, Db, b, D

qF

B, B, D

Exercice 2.2Donner l’exécution (la séquence des descriptions instantanées des configurations) de la machine que vous avez définie en question 1 sur l’entrée abbaab


a b b a a b

q0


q1

a b b a a b


q2

a b b a a b


q0

a b b a a b


q1

a b b a a b


q2

a b b a a b


q0

a b b a a b


q′

a b b a a b


q′ ′

a b b a a b


qF

a b b a a b

Exercice 2.3

Peut-on déduire de la question 1 que est : (a) récursif ? (b) récursivement énumérable ?

• est reconnu par une machine qui s’arrête toujours, donc il est (a) récursif

• Un langage récursif est toujours (b) récursivement énumérable (exercice 1.5), donc l’est aussi

L1

L1

L1

Exercice 3 Réduction many-one Turing

Exercice 3.1Montrer que , avec et

• Soit avec définie par

  simuler sur ;  si accepte alors accepter, sinon boucler à l’infini

• est calculable par une machine de Turing ; il suffit de modifier le codage en et recopier

• Maintenant il faut montrer que ssi

Lū ≤Tm L2 Lū = {⟨M⟩#w ∣ M n’accepte pas w}L2 = {⟨M⟩#w ∣ M(w) ↑ }

f(⟨M⟩#w) = ⟨M′ ⟩#w M′

M′ (x) =M x

M x

f⟨M⟩ ⟨M′ ⟩ w

⟨M⟩#w ∈ Lū f(⟨M⟩#w) = ⟨M′ ⟩#w ∈ L2

Exercice 3.1• Si alors n’accepte pas , soit parce qu’elle ne

termine pas, soit parce qu’elle s’arrête sans accepter

• Donc ne s’arrête pas sur l’entrée :


• Soit la simulation de sur ne termine pas (donc non plus), soit elle termine en rejetant et entre dans une boucle infinie

• Dans le deux cas on obtient

⟨M⟩#w ∈ Lū M w

M′ w

M′ (w) =M w

M w

M w M′ M′

⟨M′ ⟩#w ∈ L2

Exercice 3.1• Si, au contraire, alors accepte et en particulier 

elle s’arrête

• Donc s’arrête aussi sur l’entrée :


• La simulation de sur termine et donc accepte

• Donc on obtient

⟨M⟩#w ∉ Lū M w

M′ w

M′ (w) =M w

M w

M w M′

⟨M′ ⟩#w ∉ L2

Exercice 3.2

Pourquoi peut-on en déduire que n’est pas récursif ?

• On vient de démontrer que

• Dans ce cas, si était récursif, alors serait récursif aussi (exercice 1.4)

• Mais n’est pas récursivement énumérable, donc pas récursif non plus (exercice 1.5, réponse (a))

L2

Lū ≤Tm L2

L2 Lū

Lū

Exercice 4 Théorème de Rice

Exercice 4.1

Qu’est-ce qu’une propriété non triviale ?

• C’est une famille (ensemble) de langages telle que

• il existe une machine telle que

• il existe une machine telle que

P ⊆ 𝒫(Σ⋆)

M1 L(M1) ∈ P

M2 L(M2) ∉ P

Exercice 4.2Donner un exemple de propriété triviale

• L’ensemble vide est une propriété triviale, parce que pour chaque machine on a

• La famille de tous les langages est une propriété triviale, parce que pour chaque machine on a

• La famille de langages est aussi une propriété triviale, parce que , donc pour aucune machine on a

P = ∅M L(M) ∉ P

P = 𝒫(Σ⋆)M L(M) ∈ P

P = {Lū}Lū ≠ RE M

L(M) ∈ P

Exercice 4.3

Cette propriété (celle de votre réponse à la question 2) est-elle intéressante ?

• Les propriétés et sont triviales pour des raisons banales

• En revanche, est triviale mais peut-être pour des raisons un peu plus intéressantes…

P = ∅ P = 𝒫(Σ⋆)

P = {Lū}

Exercice 4.4Donner un exemple de propriété non triviale

•

• Il existe une machine de Turing qui accepte exactement tous les mots de longueur paire, donc

• Il existe aussi une machine de Turing qui accepte exactement tous les mots de longueur impaire, donc

• En général, il suffit de trouver une famille de langages qui contient au moins un langage mais pas la totalité de

P = {L ∣ tous les mots de L ont longueur paire}

M1L(M1) ∈ P

M2L(M2) ∉ P

RE RE

Exercice 4.5Que dit le théorème de Rice de cette propriété (celle de votre réponse à la question 4) ? Répondre en complétant la phrase suivante : Il n’existe pas de machine de Turing qui prenne en entrée…

• …le code d’une machine de Turing et décide, en s’arrêtant toujours, si n’accepte que des mots de longueur paire (autrement dit, si le langage de appartient à )

• En général, le langage n’est pas récursif pour toute propriété non triviale

⟨M⟩ MM

M P

LP = {⟨M⟩ ∣ L(M) ∈ P}P

Exercice 5 Bonus

Exercice 5.1Montrer que , avec et

• parle de machines qui ne s’arrêtent pas sur un certain mot , alors que parle de machines qui ne s’arrêtent jamais

• L’astuce pour cette réduction est de transformer la machine en une machine qui ne s’arrête jamais si ne s’arrête pas sur ; sinon doit s’arrêter sur au moins un mot… c’est simple de choisir lui-même !

L2 ≤Tm L∞ L2 = {⟨M⟩#w ∣ M(w) ↑ }L∞ = {⟨M⟩ ∣ M(w) ↑ pour tout w ∈ Σ⋆}

L2 Mw L∞

M M′ Mw M′

w

Exercice 5.1• On fait la réduction (fonction calculable)  

avec définie par

si alors simuler sur sinon boucler à l’infini

• La machine ne s’arrête jamais, sauf éventuellement sur

• Si alors ne s’arrête pas sur , donc ne s’arrête sur aucun mot d’entrée, donc

• Si alors s’arrête sur , donc s’arrête sur exactement un mot (notamment ), donc

f(⟨M⟩#w) = ⟨M′ ⟩M′

M′ (x) = x = w M x

M′ w

⟨M⟩#w ∈ L2 M w M′ ⟨M′ ⟩ ∈ L∞

⟨M⟩#w ∉ L2 M w M′ w ⟨M′ ⟩ ∉ L∞

Exercice 5.2Que dire de ?

• Peut-on faire aussi une réduction dans l’autre direction ?

• Il faut transformer une entrée de en une entrée tel que ne s’arrête pas sur le mot ssi ne

s’arrête sur aucune entrée

• Ça nous demande de simuler sur toutes les entrées possibles jusqu’à en trouver une sur laquelle s’arrête (ou continuer a simuler a l’infini si ça n’arrive jamais)

L∞ ≤Tm L2

⟨M⟩ L∞⟨M′ ⟩#w M′ w M

MM

Exercice 5.2• Soit une énumération de tous les mots de

• Par exemple, d’abord le mot de longueur , puis les mots de longueur en ordre lexicographique, puis les mots de longueur , etc…

• Sur l’alphabet ça donne l’énumération

w1, w2, … Σ⋆

01

2

Σ = {a, b}

ϵ, a, b, aa, ab, ba, bb,aaa, aab, aba, abb, baa, bab, bba, bbb, …

Exercice 5.2• On commence en simulant étape de sur le mot ; si accepte en

étape, on s’arrête aussi en acceptant

• Sinon, on simule étapes de sur le mot , puis étapes sur le mot ; si accepte l’un des deux mots en étapes, on s’arrête aussi en

acceptant

• Sinon, on simule étapes de sur les mots , et , en acceptant si elle accepte l’un des mots

• …

• Sinon, on simule étapes de sur les mots , en acceptant si elle accepte l’un des mots

1 M w1 M1

2 M w1 2w2 M 2

3 M w1 w2 w3

t M w1, w2, …, wt

Exercice 5.2• Ça revient à faire la réduction (fonction calculable)

avec n’importe quel fixé, par exemple , et définie par

  si alors 

soit l’énumération de  pour à faire 

pour à faire simuler étapes de sur  

si s’arrête alors accepter   sinon accepter

f(⟨M⟩) = ⟨M′ ⟩#w ww = abba M′

M′ (x) =x = w

w1, w2, … Σ⋆t := 1 ∞

i := 1 tt M wi

M

Exercice 5.2• Si alors ne s’arrête sur aucune entrée , c’est-à-dire

que pour tout , ne s’arrête pas en étapes sur aucun mot

  si alors 

soit l’énumération de  pour à faire 


si s’arrête alors accepter  sinon accepter

• Donc ne s’arrête pas sur , ce qui implique

⟨M⟩ ∈ L∞ M wit ∈ ℕ M t

M′ (x) =x = w

w1, w2, … Σ⋆t := 1 ∞

i := 1 tt M wi

M

M′ w ⟨M′ ⟩#w ∈ L2

Exercice 5.2• Si alors s’arrête sur une entrée , c’est-à-dire que pour

quelque , s’arrête en étapes sur

  si alors 

soit l’énumération de  pour à faire  


si s’arrête alors accepter  sinon accepter

• Donc s’arrête en acceptant sur , ce qui implique

⟨M⟩ ∉ L∞ M wit ∈ ℕ M t wi

M′ (x) =x = w

w1, w2, … Σ⋆t := 1 ∞

i := 1 tt M wi

M

M′ w ⟨M′ ⟩#w ∉ L2

N’hésitez pas à poser des questions !

aeporreca.org/forum-calculabilite

https://aeporreca.org/forum-calculabilite

Bon courage !

Documents

TD5 - Antonio E. Porreca · 2021. 1. 28. · Exercice 4.4 Donner un exemple de propriété non triviale • Il existe une machine de Turing qui accepte exactement tous les mots de