summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-inf105.tex6
1 files changed, 3 insertions, 3 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 6bb7d6d..3806498 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3211,7 +3211,7 @@ suffit donc de prendre $i=0$ pour avoir une contradiction.
\subsection{L'automate minimal, et la minimisation}
-\begin{thm}[Myhill-Nerode]\label{myhill-nerode}
+\begin{thm}[Myhill-Nerode]\label{myhill-nerode}\index{Myhill-Nerode (théorème de)}
Soit $L$ un langage. Pour $w\in \Sigma^*$, notons $w^{-1} L := \{t
\in \Sigma^* : wt \in L\}$ (autrement dit, l'ensemble des mots qu'on
peut concaténer à $w$ pour obtenir un mot de $L$). Considérons la
@@ -5175,7 +5175,7 @@ que c'est cet ensemble-là qui la fait fonctionner.
rien au résultat comme on peut le voir en appliquant le théorème
s-m-n.)\par}
-\begin{thm}[Turing]
+\begin{thm}[Turing]\index{Turing (théorème de)}
Le problème de l'arrêt est semi-décidable mais non décidable.
\end{thm}
\begin{proof}
@@ -5224,7 +5224,7 @@ semi-décidable, son complémentaire ne l'est pas.
\end{proof}
{\footnotesize\thingy\textbf{Complément :} L'argument diagonal est
- aussi au cœur du (voire, équivalent au) \emph{théorème de récursion
+ aussi au cœur du (voire, équivalent au) \index{Kleene (théorème de récursion de)}\emph{théorème de récursion
de Kleene}, qui affirme que pour toute fonction calculable
partielle $h\colon\mathbb{N}^2\dasharrow\mathbb{N}$, il existe $p$
tel que $\varphi_p(n) = h(p,n)$ pour tout $n$ (la signification