diff options
| -rw-r--r-- | notes-inf105.tex | 309 |
1 files changed, 184 insertions, 125 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 8ee32d7..60877a5 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -5686,7 +5686,7 @@ construits (et éventuellement les arbres eux-mêmes). \section{Introduction à la calculabilité}\label{section-computability} -\setcounter{comcnt}{0} +\subsection{Présentation générale} \thingy\textbf{Discussion préalable.} On s'intéresse ici à la question de savoir ce qu'un \defin{algorithme} peut ou ne peut pas faire. @@ -5703,7 +5703,7 @@ décidable par un algorithme ou que telle ou telle fonction est calculable par un algorithme deviennent beaucoup moins lisibles quand on les formalise avec une définition rigoureuse d'algorithme (notamment, programmer une machine de Turing est encore plus -fastidieux que programmer en assembleur un ordinateur, donc s'il +fastidieux que programmer un ordinateur en assembleur, donc s'il s'agit d'exhiber un algorithme, c'est probablement une mauvaise idée de l'écrire sous forme de machine de Turing). @@ -5721,9 +5721,10 @@ notion de fonction calculable ou calculable partielle, définie ci-dessous). La \defin[Church-Turing (thèse de)]{thèse de Church-Turing} affirme, au moins informellement, que tout ce qui est effectivement calculable par un algorithme\footnote{Voire, dans - certaines variantes, physiquement calculable dans notre Univers.} -est calculable par n'importe laquelle de ces notions formelles -d'algorithmes, qu'on peut rassembler sous le nom commun de + certaines variantes de la thèse, tout ce qui est physiquement + calculable dans notre Univers (y compris par des processus + quantiques).} est calculable par n'importe laquelle de ces notions +formelles d'algorithmes, qu'on peut rassembler sous le nom commun de \defin[calculable (fonction)]{calculabilité au sens de Church-Turing}, ou « calculabilité » tout court. @@ -5739,7 +5740,7 @@ entiers, chaînes de caractère, tableaux, etc., de taille arbitraire c'est-à-dire équivalents dans leur pouvoir de calcul à la calculabilité de Church-Turing. Pour imaginer intuitivement la calculabilité, on peut donc choisir le langage qu'on préfère et -imaginer qu'on programme dedans. Essentiellement, pour qu'un langage +imaginer qu'on programme dedans. Dans la pratique, pour qu'un langage soit Turing-complet, il lui suffit d'être capable de manipuler des entiers de taille arbitraire, de les comparer et de calculer les opérations arithmétiques dessus, et d'effectuer des tests et des @@ -5756,28 +5757,64 @@ pour arguër qu'il existe un algorithme qui décide si un entier naturel $n$ est premier ou non, il suffit de dire qu'on peut calculer tous les produits $pq$ avec $2\leq p,q\leq n-1$ et tester si l'un d'eux est égal à $n$, peu importe que cet algorithme soit absurdement -inefficace. De même, nos algorithmes sont capables de manipuler des -entiers arbitrairement grands : ceci permet de dire, par exemple, que -toute chaîne binaire peut être considérée comme un entier, peu importe -le fait que cet entier ait peut-être des milliards de chiffres (dans -les langages informatiques réels, on a rarement envie de considérer -toute donnée comme un entier, mais en calculabilité on peut se -permettre de le faire). - -Notamment, plutôt que de considérer des « mots » (éléments -de $\Sigma^*$ avec $\Sigma$ un alphabet fini) et « langages » (parties -de $\Sigma^*$), il sera plus pratique de remplacer l'ensemble -$\Sigma^*$ des mots par l'ensemble des entiers naturels, quitte à -choisir un codage (calculable !) des mots par des entiers. (À titre -d'exemple, on obtient une bijection de l'ensemble $\{0,1\}^*$ des mots -sur l'alphabet à deux lettres avec $\mathbb{N}$ de la façon suivante : -ajouter un $1$ au début du mot, lire celui-ci comme un nombre binaire, -et soustraire $1$. Plus généralement, une fois choisi un ordre total -sur l'alphabet fini $\Sigma$, on peut trier les mots par ordre de -taille, et, à taille donnée, par ordre lexicographique, et leur -associer les entiers naturels dans le même ordre : il n'est pas -difficile de montrer que cela donne bien une bijection calculable -entre $\Sigma^*$ et $\mathbb{N}$.) +inefficace. + +De même, nos algorithmes sont capables de manipuler des entiers +arbitrairement grands : ceci permet de dire, par exemple, que toute +chaîne binaire peut être considérée comme un entier, peu importe le +fait que cet entier ait peut-être des milliards de chiffres ; dans les +langages informatiques réels, on a rarement envie de considérer toute +donnée comme un entier, mais en calculabilité on peut se permettre de +le faire. + +\thingy\label{computability-all-data-are-integers} Soulignons et +développons le point esquissé au paragraphe précédent : plutôt que de +travailler avec des « mots » (éléments de $\Sigma^*$ avec $\Sigma$ un +alphabet fini), en calculabilité, il est possible, dès que cela est +commode, de remplacer ceux-ci par des entiers naturels. + +Il suffit pour cela de choisir un « codage », parfois appelé +\defin{codage de Gödel} permettant de représenter un élément de +$\Sigma^*$ par un entier naturel : la chose importante est que la +conversion d'un mot en entier ou d'un entier en mot soit calculable +par un algorithme (même très inefficace), si bien que toute +manipulation algorithmique sur des mots puisse être convertie en +manipulation sur des entiers. Il est commode pour simplifier les +raisonnements (quoique pas indispensable) de supposer que le codage +est bijectif, c'est-à-dire qu'on dispose d'une bijection $\mathbb{N} +\to \Sigma^*$ algorithmiquement calculable et dont la réciproque l'est +aussi. + +Il existe toutes sortes de manières d'obtenir un tel codage. La plus +simple est sans doute la suivante : une fois choisi un ordre total +arbitraire sur l'alphabet (fini !) $\Sigma$, on peut énumérer les mots +sur $\Sigma$ par ordre de taille et, pour une taille donnée, par ordre +lexicographique (par exemple : $\varepsilon, a, b,\penalty0 aa, ab, +ba, bb, aaa, aab...$ sur l'alphabet $\{a,b\}$) ; cette énumération est +visiblement faisable algorithmiquement, et quitte à numéroter au fur +et à mesure qu'on énumère, on obtient un codage comme souhaité (par +exemple $0 \leftrightarrow\varepsilon$, $1 \leftrightarrow a$, $2 +\leftrightarrow b$, $3 \leftrightarrow ab$, etc.). Insistons sur le +fait que ce n'est là qu'une possibilité parmi d'autres et que les +détails du codage sont sans importance tant qu'il est calculable ; +l'important est que ce soit faisable en théorie et donc qu'on peut +considérer qu'au lieu de mots on a affaire à des entiers naturels. + +Il va de soi que la concaténation de deux mots, la longueur d'un mot, +le miroir d'un mot, sont tous calculables algorithmiquement. + +On peut considérer que, dans cette partie, le terme de +\index{langage}« langage » désigne non plus une partie de $\Sigma^*$ +mais une partie de $\mathbb{N}$. + +{\footnotesize (Le remplacement des mots par des entiers naturels en + utilisant un codage comme on vient de le dire est assez standard en + calculabilité. Il ne doit pas dérouter : on peut imaginer qu'on a + affaire à $\Sigma^*$ à chaque fois qu'il est question + de $\mathbb{N}$ ci-dessous, et on a toujours affaire à la théorie + des langages. Le point central est justement que cela n'a pas + d'importance ; comme $\mathbb{N}$ est un objet mathématiquement plus + simple, c'est surtout pour cela qu'il est utilisé à la place.)\par} \medbreak @@ -5786,25 +5823,28 @@ effectue un calcul utile doit certainement terminer en temps fini. Néanmoins, même si on voudrait ne s'intéresser qu'à ceux-ci, il n'est pas possible d'ignorer le « problème » des algorithmes qui ne terminent jamais (et ne fournissent donc aucun résultat). C'est le -point central de la calculabilité (et du théorème de Turing -ci-dessous) qu'on ne peut pas se débarrasser des algorithmes qui ne -terminent pas : on ne peut pas, par exemple, formaliser une notion -suffisante\footnote{Tout dépend, évidemment, de ce qu'on appelle - « suffisant » : il existe bien des notions de calculabilité, plus - faibles que celle de Church-Turing, où tout calcul termine, voir par - exemple la notion de fonction « primitive récursive » ou le langage - « BlooP » de Hofstadter ; mais de telles notions ne peuvent pas - disposer d'une machine universelle comme expliqué plus loin (en - raison d'un argument diagonal), donc elles sont nécessairement - incomplètes en un certain sens.} de calculabilité dans laquelle tout -algorithme termine toujours ; ni développer un langage de -programmation suffisamment général dans lequel il est impossible qu'un -programme « plante » indéfiniment ou parte en boucle infinie. (Cette -subtilité est d'ailleurs sans doute en partie responsable de la -difficulté historique à dégager la bonne notion d'« algorithme » : on -a commencé par développer des notions d'algorithmes terminant -forcément, comme les fonctions primitives récursives, et on se rendait -bien compte que ces notions étaient forcément toujours incomplètes.) +point central de la calculabilité (et du théorème de +Turing \ref{undecidability-of-halting-problem} ci-dessous) qu'on ne +peut pas se débarrasser des algorithmes qui ne terminent pas : on ne +peut pas, par exemple, formaliser une notion suffisante\footnote{Tout + dépend, évidemment, de ce qu'on appelle « suffisant » : il existe + bien des notions de calculabilité, plus faibles que celle de + Church-Turing, où tout calcul termine, voir par exemple la notion de + fonction « primitive récursive » ou le langage « BlooP » de + Hofstadter ; mais de telles notions ne peuvent pas disposer d'une + machine universelle comme expliqué plus loin (en raison d'un + argument diagonal), donc elles sont nécessairement incomplètes en un + certain sens.} de calculabilité dans laquelle tout algorithme +termine toujours ; ni développer un langage de programmation +suffisamment général dans lequel il est impossible qu'un programme +« plante » indéfiniment ou parte en boucle infinie. + +{\footnotesize (Cette subtilité est d'ailleurs sans doute en partie + responsable de la difficulté historique à dégager la bonne notion + d'« algorithme » : on a commencé par développer des notions + d'algorithmes terminant forcément, comme les fonctions primitives + récursives, et on se rendait bien compte que ces notions étaient + forcément toujours incomplètes.)\par} \bigbreak @@ -5815,13 +5855,13 @@ On dit qu'une fonction $f\colon\mathbb{N}\to\mathbb{N}$ est algorithme qui prend en entrée $n\in\mathbb{N}$, termine toujours en temps fini, et calcule (renvoie) $f(n)$. -On dit qu'un ensemble $A \subseteq \mathbb{N}$ (« langage ») est -\defin{décidable} (ou \index{calculable - (langage)|see{décidable}}« calculable » ou \index{récursif - (langage)|see{décidable}}« récursif ») lorsque sa fonction -indicatrice $\mathbf{1}_A \colon \mathbb{N} \to \mathbb{N}$ (valant -$1$ sur $A$ et $0$ sur son complémentaire) est calculable. Autrement -dit : lorsqu'il existe un algorithme qui prend en entrée +On dit qu'un ensemble $A \subseteq \mathbb{N}$ (un « langage », +cf. \ref{computability-all-data-are-integers}) est \defin{décidable} +(ou \index{calculable (langage)|see{décidable}}« calculable » ou +\index{récursif (langage)|see{décidable}}« récursif ») lorsque sa +fonction indicatrice $\mathbf{1}_A \colon \mathbb{N} \to \mathbb{N}$ +(valant $1$ sur $A$ et $0$ sur son complémentaire) est calculable. +Autrement dit : lorsqu'il existe un algorithme qui prend en entrée $n\in\mathbb{N}$, termine toujours en temps fini, et renvoie « oui » ($1$) si $n\in A$, « non » ($0$) si $n\not\in A$ (on dira que l'algorithme « décide » $A$). @@ -5832,10 +5872,14 @@ définie sur une partie de $\mathbb{N}$, appelé ensemble de définition de $f$) est \defin[calculable partielle (fonction)]{calculable partielle} (ou « récursive partielle ») lorsqu'il existe un algorithme qui prend en entrée $n\in\mathbb{N}$, termine en temps fini -ssi $f(n)$ est définie, et dans ce cas calcule (renvoie) $f(n)$. (Une -fonction calculable est donc simplement une fonction calculable -partielle qui est toujours définie : on dira parfois « calculable -totale » pour souligner ce fait.) +si et seulement si $f(n)$ est définie, et dans ce cas calcule +(renvoie) $f(n)$. (Une fonction calculable est donc simplement une +fonction calculable partielle qui est toujours définie : on dira +parfois « calculable totale » pour souligner ce fait.) + +On utilisera la notation $f(n)\downarrow$ pour signifier le fait que +la fonction calculable partielle $f$ est définie en $n$, c'est-à-dire, +que l'algorithme en question termine. On dit qu'un ensemble $A \subseteq \mathbb{N}$ est \defin{semi-décidable} (ou \index{semi-calculable @@ -5844,11 +5888,12 @@ On dit qu'un ensemble $A \subseteq \mathbb{N}$ est lorsque la fonction partielle $\mathbb{N}\dasharrow\mathbb{N}$ définie exactement sur $A$ et y valant $1$, est calculable partielle. Autrement dit : lorsqu'il existe un algorithme qui prend en entrée -$n\in\mathbb{N}$, termine en temps fini ssi $n \in A$, et renvoie -« oui » ($1$) dans ce cas\footnote{En fait, la valeur renvoyée n'a pas - d'importance ; on peut aussi définir un ensemble semi-décidable - comme l'ensemble de définition d'une fonction calculable partielle.} -(on dira que l'algorithme « semi-décide » $A$). +$n\in\mathbb{N}$, termine en temps fini si et seulement si $n \in A$, +et renvoie « oui » ($1$) dans ce cas\footnote{En fait, la valeur + renvoyée n'a pas d'importance ; on peut aussi définir un ensemble + semi-décidable comme l'ensemble de définition d'une fonction + calculable partielle.} (on dira que l'algorithme +« semi-décide » $A$). \end{defn} On s'est limité ici à des fonctions d'une seule variable (entière), @@ -5894,10 +5939,14 @@ affaire à un seul paramètre entier. parfaits, des nombres premiers, sont décidables, c'est-à-dire qu'il est algorithmique de savoir si un nombre est pair, parfait, ou premier. Quitte éventuellement à coder les mots d'un alphabet fini -comme des entiers naturels (cf. plus haut), tout langage rationnel, et -même tout langage défini par une grammaire hors contexte, est -décidable. On verra plus bas des exemples d'ensembles qui ne le sont -pas, et qui sont ou ne sont pas semi-décidables. +comme des entiers naturels +(cf. \ref{computability-all-data-are-integers}), tout langage +rationnel, et même tout langage défini par une grammaire hors +contexte, est décidable (cf. \ref{rational-languages-are-recognizable} +et \ref{algebraic-languages-are-decidable}). + +On verra plus bas des exemples d'ensembles qui ne le sont pas, et qui +sont ou ne sont pas semi-décidables. \medbreak @@ -5906,8 +5955,8 @@ servent à donner des exemples du genre de manipulation qu'on peut faire avec la notion de calculabilité et d'algorithme : \begin{prop}\label{decidable-iff-semidecidable-and-complement} -Un ensemble $A \subseteq \mathbb{N}$ est décidable ssi $A$ et -$\mathbb{N}\setminus A$ sont tous les deux semi-décidables. +Un ensemble $A \subseteq \mathbb{N}$ est décidable si et seulement si +$A$ et $\mathbb{N}\setminus A$ sont tous les deux semi-décidables. \end{prop} \begin{proof} Il est évident qu'un ensemble décidable est semi-décidable (si un @@ -5928,10 +5977,12 @@ de décider algorithmiquement si $n \in A$ ou $n \not\in A$. \end{proof} \begin{prop} -Un ensemble $A \subseteq \mathbb{N}$ non vide est semi-décidable ssi -il existe une fonction calculable $f \colon \mathbb{N} \to \mathbb{N}$ -dont l'image ($f(\mathbb{N})$) vaut $A$ (on dit aussi que $A$ est -« calculablement énumérable » ou « récursivement énumérable »). +Un ensemble $A \subseteq \mathbb{N}$ non vide est semi-décidable si et +seulement si il existe une fonction calculable $f \colon \mathbb{N} +\to \mathbb{N}$ dont l'image ($f(\mathbb{N})$) vaut $A$ (on dit aussi +que $A$ est « \defin{calculablement énumérable} » ou +« \index{récursivement énumérable|see{calculablement + énumérable}}récursivement énumérable »). \end{prop} \begin{proof} Montrons qu'un ensemble semi-décidable non vide est calculablement @@ -5957,7 +6008,7 @@ termine jamais puisqu'il effectue une boucle infinie à la recherche d'un tel $k$). \end{proof} -{\footnotesize\thingy\textbf{Clarification :} Les deux démonstrations +{\footnotesize\thingy\textbf{Éclaircissement :} Les deux démonstrations ci-dessus font appel à la notion intuitive d'« étape » de l'exécution d'un algorithme. Un peu plus précisément, pour chaque entier $m$ et chaque algorithme $T$, il est possible d'« exécuter au @@ -5975,8 +6026,8 @@ d'un tel $k$). de $T$ résultat.\par} {\footnotesize\thingy\textbf{Complément/exercice :} Un ensemble $A - \subseteq \mathbb{N}$ infini est décidable ssi il existe une - fonction calculable $f \colon \mathbb{N} \to \mathbb{N}$ + \subseteq \mathbb{N}$ infini est décidable si et seulement si il + existe une fonction calculable $f \colon \mathbb{N} \to \mathbb{N}$ \underline{strictement croissante} dont l'image vaut $A$. (Esquisse : si $A$ est décidable, on peut trouver son $n$-ième élément par ordre croissant en testant l'appartenance à $A$ de tous @@ -5990,28 +6041,33 @@ d'un tel $k$). l'ensemble et jeter toute valeur qui n'est pas strictement plus grande que toutes les précédentes).\par} -\bigbreak +\subsection{Machine universelle, et problème de l'arrêt} \thingy\textbf{Codage et machine universelle.} Les algorithmes sont eux-mêmes représentables par des mots sur un alphabet fini donc, si on -préfère, par des entiers naturels : on parle aussi de \defin{codage - de Gödel} des algorithmes/programmes par des entiers. On obtient -donc une énumération $\varphi_0, \varphi_1, \varphi_2, -\varphi_3\ldots$ de toutes les fonctions calculables partielles (la -fonction $\varphi_e$ étant la fonction que calcule l'algorithme [codé - par l'entier] $e$, avec la convention que si cet algorithme est -syntaxiquement invalide ou erroné pour une raison quelconque, la -fonction $\varphi_e$ est simplement non-définie partout). Les détails -de cette énumération dépendent de la formalisation utilisée pour la -calculabilité. +préfère (cf. \ref{computability-all-data-are-integers}), par des +entiers naturels : on parle aussi de \defin{codage de Gödel} des +algorithmes/programmes par des entiers. On obtient donc une +énumération $\varphi_0, \varphi_1, \varphi_2, \varphi_3\ldots$ de +toutes les fonctions calculables partielles (la fonction $\varphi_e$ +étant la fonction que calcule l'algorithme [codé par l'entier] $e$, +avec la convention que si cet algorithme est syntaxiquement invalide +ou erroné pour une raison quelconque, la fonction $\varphi_e$ est +simplement non-définie partout). Les détails de cette énumération +dépendent de la formalisation utilisée pour la calculabilité et ne +sont pas importants\footnote{Par exemple, ceux qui aiment le langage + Java, peuvent considérer que $\varphi_e$ désigne le résultat de + l'exécution du programme Java représenté par le mot codé par $e$, si + ce programme est valable (remplacer Java par tout autre langage + préféré).}. Un point crucial dans cette numérotation des algorithmes est l'existence d'une \defin[universelle (machine)]{machine universelle}, c'est-à-dire d'un algorithme $U$ qui prend en entrée un entier $e$ (codant un algorithme $T$) et un entier $n$, et effectue la même chose que $T$ sur l'entrée $n$ (i.e., $U$ termine sur les entrées $e$ et $n$ -ssi $T$ termine sur l'entrée $n$, et, dans ce cas, renvoie la même -valeur). +si et seulement si $T$ termine sur l'entrée $n$, et, dans ce cas, +renvoie la même valeur). Informatiquement, ceci représente le fait que les programmes informatiques sont eux-mêmes représentables informatiquement : dans un @@ -6043,14 +6099,15 @@ programmation demande un minimum d'efforts). fonctions calculables partielles. $\bullet$ Le \emph{théorème de la forme normale de Kleene} assure qu'il existe un ensemble \underline{décidable} $\mathscr{T} \subseteq \mathbb{N}^4$ tel que - $\varphi_e(n)$ soit défini ssi il existe $m,v$ tels que $(e,n,m,v) - \in \mathscr{T}$, et dans ce cas $\varphi_e(n) = v$ (pour s'en - convaincre, il suffit de définir $\mathscr{T}$ comme l'ensemble des - $(e,n,m,v)$ tels que le $e$-ième algorithme exécuté sur l'entrée $n$ - termine en au plus $m$ étapes et renvoie le résultat $v$ : le fait - qu'on dispose d'une machine universelle et qu'on puisse exécuter $m$ - étapes d'un algorithme assure que cet ensemble est bien décidable — - il est même « primitif récursif »). $\bullet$ Le \emph{théorème + $\varphi_e(n)$ soit défini si et seulement si il existe $m,v$ tels + que $(e,n,m,v) \in \mathscr{T}$, et dans ce cas $\varphi_e(n) = v$ + (pour s'en convaincre, il suffit de définir $\mathscr{T}$ comme + l'ensemble des $(e,n,m,v)$ tels que le $e$-ième algorithme exécuté + sur l'entrée $n$ termine en au plus $m$ étapes et renvoie le + résultat $v$ : le fait qu'on dispose d'une machine universelle et + qu'on puisse exécuter $m$ étapes d'un algorithme assure que cet + ensemble est bien décidable — il est même « primitif + récursif »). $\bullet$ Le \index{s-m-n (théorème)}\emph{théorème s-m-n} assure qu'il existe une fonction calculable $s$ telle que $\varphi_{s(e,\underline{m})}(\underline{n}) = \varphi_e(\underline{m},\underline{n})$ (intuitivement, donné un @@ -6068,8 +6125,8 @@ programmation demande un minimum d'efforts). La machine universelle n'a rien de « magique » : elle se contente de suivre les instructions de l'algorithme $T$ qu'on lui fournit, et -termine ssi $T$ termine. Peut-on savoir à l'avance si $T$ terminera ? -C'est le fameux « problème de l'arrêt ». +termine si et seulement si $T$ termine. Peut-on savoir à l'avance si +$T$ terminera ? C'est le fameux « problème de l'arrêt ». \smallbreak @@ -6101,7 +6158,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]\index{Turing (théorème de)} +\begin{thm}[Turing]\index{Turing (théorème de)}\label{undecidability-of-halting-problem} Le problème de l'arrêt est semi-décidable mais non décidable. \end{thm} \begin{proof} @@ -6136,16 +6193,17 @@ lui-même, donc on regarde la diagonale de la fonction de deux variables $(e,n) \mapsto \varphi_e(n)$ ; en modifiant les valeurs sur cette diagonale, on produit une fonction qui ne peut pas se trouver dans une ligne $\varphi_p$.) Une variante facile du même argument -permet de fabriquer des ensembles non semi-décidables (voir le -« bonus » ci-dessous), ou bien on peut appliquer ce qui précède : +permet de fabriquer des ensembles non semi-décidables (voir +\ref{example-set-of-total-functions} ci-dessous), ou bien on peut +appliquer ce qui précède : \begin{cor} Le complémentaire du problème de l'arrêt n'est pas semi-décidable. \end{cor} \begin{proof} On a vu que le problème de l'arrêt n'est pas décidable, et qu'un -ensemble est décidable ssi il est semi-décidable et que son -complémentaire l'est aussi : comme le problème de l'arrêt est bien +ensemble est décidable si et seulement si il est semi-décidable et que +son complémentaire l'est aussi : comme le problème de l'arrêt est bien semi-décidable, son complémentaire ne l'est pas. \end{proof} @@ -6180,31 +6238,32 @@ directement : pour montrer qu'un certain ensemble $A$ (un un algorithme décidant $A$ existait, on pourrait s'en servir pour construire un algorithme résolvant le problème de l'arrêt. -{\footnotesize\thingy\textbf{Bonus / exemple(s) :} L'ensemble des $e - \in \mathbb{N}$ tels que la fonction calculable partielle - $\varphi_e$ soit \underline{totale} (i.e., définie sur - tout $\mathbb{N}$) n'est pas semi-décidable. En effet, s'il - l'était, d'après ce qu'on a vu, il serait « calculablement - énumérable », c'est-à-dire qu'il existerait une fonction calculable - $f\colon\mathbb{N}\to\mathbb{N}$ dont l'image soit exactement - l'ensemble des $e$ pour lesquels $\varphi_e$ est totale, i.e., toute - fonction calculable totale s'écrirait sous la forme $\varphi_{f(k)}$ - pour un certain $k$. Mais la fonction $n \mapsto \varphi_{f(n)}(n) - + 1$ est calculable totale, donc il devrait exister un $m$ tel que - cette fonction s'écrive $\varphi_{f(m)}$, c'est-à-dire - $\varphi_{f(m)}(n) = \varphi_{f(n)}(n) + 1$, et on aurait alors en - particulier $\varphi_{f(m)}(m) = \varphi_{f(m)}(m) + 1$, une +{\footnotesize\thingy\label{example-set-of-total-functions}\textbf{Bonus + / exemple(s) :} L'ensemble des $e \in \mathbb{N}$ tels que la + fonction calculable partielle $\varphi_e$ soit \underline{totale} + (i.e., définie sur tout $\mathbb{N}$) n'est pas semi-décidable. En + effet, s'il l'était, d'après ce qu'on a vu, il serait + « calculablement énumérable », c'est-à-dire qu'il existerait une + fonction calculable $f\colon\mathbb{N}\to\mathbb{N}$ dont l'image + soit exactement l'ensemble des $e$ pour lesquels $\varphi_e$ est + totale, i.e., toute fonction calculable totale s'écrirait sous la + forme $\varphi_{f(k)}$ pour un certain $k$. Mais la fonction $n + \mapsto \varphi_{f(n)}(n) + 1$ est calculable totale, donc il + devrait exister un $m$ tel que cette fonction s'écrive + $\varphi_{f(m)}$, c'est-à-dire $\varphi_{f(m)}(n) = + \varphi_{f(n)}(n) + 1$, et on aurait alors en particulier + $\varphi_{f(m)}(m) = \varphi_{f(m)}(m) + 1$, une contradiction. $\bullet$ Son complémentaire, c'est-à-dire l'ensemble des $e \in \mathbb{N}$ tels que la fonction calculable partielle $\varphi_e$ \underline{ne soit pas} totale, n'est pas non plus semi-décidable. En effet, supposons qu'il existe un algorithme qui, - donné $e$, termine ssi $\varphi_e$ n'est pas totale. Donnés $e$ et - $m$, considérons l'algorithme qui prend une entrée $n$, - \emph{ignore} celle-ci, et effectue le calcul $\varphi_e(m)$ : ceci - définit une fonction calculable partielle (soit totale et constante, - soit définie nulle part !) $\varphi_{s(e,m)}$ où $s$ est calculable - (on applique ici le théorème s-m-n) — en appliquant à $s(e,m)$ - l'algorithme supposé semi-décider si une fonction récursive + donné $e$, termine si et seulement si $\varphi_e$ n'est pas totale. + Donnés $e$ et $m$, considérons l'algorithme qui prend une entrée + $n$, \emph{ignore} celle-ci, et effectue le calcul $\varphi_e(m)$ : + ceci définit une fonction calculable partielle (soit totale et + constante, soit définie nulle part !) $\varphi_{s(e,m)}$ où $s$ est + calculable (on applique ici le théorème s-m-n) — en appliquant à + $s(e,m)$ l'algorithme supposé semi-décider si une fonction récursive partielle est non-totale, on voit qu'ici il semi-décide si $\varphi_e(m)$ est non-défini, autrement dit on semi-décide le complémentaire du problème de l'arrêt, et on a vu que ce n'était pas |