diff options
| -rw-r--r-- | exercices3.tex | 65 |
1 files changed, 65 insertions, 0 deletions
diff --git a/exercices3.tex b/exercices3.tex index 4964c05..f9e4917 100644 --- a/exercices3.tex +++ b/exercices3.tex @@ -287,6 +287,71 @@ L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui prouve (1). \end{corrige} +% +% +% + +\exercice + +Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième algorithme +(ou, si on préfère, de la $e$-ième machine de Turing) quand on lui +fournit le nombre $n$ en entrée, à supposer que cette exécution +termine ; sinon, $S(e,n)$ n'est pas défini. + +Soit par ailleurs $M(k)$ le maximum des $S(e,n)$ pour $0\leq e\leq k$ +et $0\leq n\leq k$ qui soient définis (et $0$ si aucun d'eux n'est +défini). Autrement dit, il s'agit du plus petit entier supérieur ou +égal au nombre d'étapes de l'exécution de l'un des algorithmes $0\leq +e\leq k$ sur l'un des entiers $0\leq n\leq k$ en entrée, lorsqu'ils +terminent. + +Montrer que la fonction $M$ n'est pas calculable (i.e., n'est pas +calculable par un algorithme) : on pourra pour cela montrer que la +connaissance de $M$ permet de résoudre le problème de l'arrêt. +Montrer même qu'\emph{aucune} fonction $M'$ telle que $M'(k) \geq +M(k)$ pour tout $k$ n'est calculable. Montrer que même si $M'$ +vérifie simplement $M'(k)\geq M(k)$ pour $k\geq k_0$, alors $M'$ n'est +pas calculable. Bref, la fonction $M$ croît plus vite que n'importe +quelle fonction calculable. + +\emph{Remarque :} La fonction $M$, ou différentes variantes de +celle-ci, s'appelle fonction du « castor affairé ». On peut montrer +encore plus fort : si $M'(k)\geq M(k)$ pour un nombre infini de +valeurs de $k$, alors $M'$ n'est pas calculable (Radó, 1962, +\textit{On Non-Computable Functions}). + +\begin{corrige} +Supposons que $M$ soit calculable. On peut alors résoudre le problème +de l'arrêt de la manière suivante : donné un algorithme $T$, de +numéro $e$, et une entrée $n$ à fournir à cet algorithme, pour savoir +si $T$ s'arrête, on calcule $M(k)$ où $k = \max(e,n)$, on exécute +ensuite l'algorithme $T$ pendant au plus $M(k)$ étapes : s'il termine +dans le temps imparti, on répond vrai (il a terminé), sinon, on répond +faux (il ne terminera jamais). Cette résolution du problème de +l'arrêt est correcte, car si $T$ termine sur l'entrée $n$, il prendra +par définition $S(e,n)$ étapes, avec $0\leq e\leq k$ et $0\leq n\leq +k$ par définition de $k$, donc $S(e,n) \leq M(k)$ par définition de +$M(k)$ : ceci signifie précisément que si $T$ n'a pas terminé en +$M(k)$ étapes, il ne terminera jamais. + +Exactement le même argument montre que $M'$ n'est pas calculable sous +l'hypothèse que $M'(k) \geq M(k)$ pour tout $k$ : s'il l'était, on +pourrait exécuter l'algorithme $T$ pendant au plus $M'(k)$ étapes, et +comme on a $S(e,n) \leq M(k) \leq M'(k)$, la même démonstration +convient. + +Enfin, si on suppose seulement $M'(k)\geq M(k)$ pour $k\geq k_0$, la +fonction $M'$ n'est toujours pas calculable : en effet, si on suppose +par l'absurde qu'elle l'est, la fonction $M''$ qui à $k$ associe +$M'(k)$ si $k\geq k_0$ et $M(k)$ sinon, serait encore calculable +puisqu'elle ne diffère de $M'$ qu'en un nombre fini de valeurs, or +changer la valeur en un point d'une fonction calculable donne toujours +une fonction calculable (même si on « ne connaît pas » la valeur à +changer, elle existe, donc l'algorithme modifié existe). Mais d'après +le paragraphe précédent, $M''$ n'est pas calculable puisqu'elle est +partout supérieure ou égale à $M$. +\end{corrige} + % % |