summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-04 17:56:21 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-04 17:56:21 +0100
commitd558a79e0f5c5e1874adfdc70bb671c8453da811 (patch)
treed9022da123e1510f2e0c3a11482fda4c47ad81a1
parentff0541e82e1a6a55fa7e29fa90fed0aa9c35639d (diff)
downloadinf105-d558a79e0f5c5e1874adfdc70bb671c8453da811.tar.gz
inf105-d558a79e0f5c5e1874adfdc70bb671c8453da811.tar.bz2
inf105-d558a79e0f5c5e1874adfdc70bb671c8453da811.zip
Be slightly more precise on what is expected about computability.
-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.