diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 6 |
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 |