From d558a79e0f5c5e1874adfdc70bb671c8453da811 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 4 Nov 2016 17:56:21 +0100
Subject: Be slightly more precise on what is expected about computability.

---
 programme-inf105.tex | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

(limited to 'programme-inf105.tex')

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.
 
 
-- 
cgit v1.2.3

