diff options
| -rw-r--r-- | programme-inf105.tex | 6 |
1 files changed, 5 insertions, 1 deletions
diff --git a/programme-inf105.tex b/programme-inf105.tex index 450ece8..2e62994 100644 --- a/programme-inf105.tex +++ b/programme-inf105.tex @@ -135,7 +135,11 @@ d'un algorithme, thèse de Church-Turing. Ensembles/langages\footnote{Souligner qu'ici contrairement au reste du cours, on peut indifféremment considérer des ensembles d'entiers naturels ou de mots.} décidables (=calculables, =récursifs) et -semi-décidables (=semi-calculables, =récursivement énumérables). +semi-décidables (=semi-calculables, =récursivement énumérables). Un +ensemble est décidable ssi lui et son complémentaire sont +semi-décidables. Un ensemble est semi-décidable ssi il est (vide ou) +énuméré par une fonction calculable. + Notion de machine universelle. Indécidabilité du problème de l'arrêt. |