diff options
| author | David A. Madore <david+git@madore.org> | 2016-11-04 17:56:21 +0100 |
|---|---|---|
| committer | David A. Madore <david+git@madore.org> | 2016-11-04 17:56:21 +0100 |
| commit | d558a79e0f5c5e1874adfdc70bb671c8453da811 (patch) | |
| tree | d9022da123e1510f2e0c3a11482fda4c47ad81a1 | |
| parent | ff0541e82e1a6a55fa7e29fa90fed0aa9c35639d (diff) | |
| download | inf105-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.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. |