From d558a79e0f5c5e1874adfdc70bb671c8453da811 Mon Sep 17 00:00:00 2001 From: "David A. Madore" 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(-) 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