summaryrefslogtreecommitdiffstats
path: root/programme-inf105.tex
diff options
context:
space:
mode:
Diffstat (limited to 'programme-inf105.tex')
-rw-r--r--programme-inf105.tex6
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.