diff options
Diffstat (limited to 'exercices-inf110.tex')
| -rw-r--r-- | exercices-inf110.tex | 17 |
1 files changed, 8 insertions, 9 deletions
diff --git a/exercices-inf110.tex b/exercices-inf110.tex index d43d56f..4613d8b 100644 --- a/exercices-inf110.tex +++ b/exercices-inf110.tex @@ -274,7 +274,7 @@ décidable. \textbf{(2)} Soit $H := \{d \in \mathbb{N} : \varphi^{(1)}_d(0)\downarrow\}$ (variante du problème de l'arrêt). Rappeler brièvement pourquoi $H$ est semi-décidable mais non -décidable, et pourquoi son complémentair $\complement H$ n'est pas +décidable, et pourquoi son complémentaire $\complement H$ n'est pas semi-décidable. \textbf{(3)} Montrer qu'il existe une fonction $\rho \colon \mathbb{N} @@ -512,8 +512,8 @@ dont l'\emph{extension} est primitive récursive ; \textit{grosso Manifestement, $M \subseteq N$, car si $\psi^{(1)}_e$ est définie, on a $\varphi^{(1)}_e = \psi^{(1)}_e$ (la définition des fonctions générales récursives \emph{étend} celle des fonctions p.r.). -L'inclusion dans l'autre sens ne vaut pas : on peut calculer la -fonction constante nulle en faisant une boucle infinie, ce qui fournit +L'inclusion dans l'autre sens ne vaut pas : on peut calculer une +fonction non p.r., jeter le résultat, et renvoyer $0$, ce qui fournit un code $e$ tel que $\varphi^{(1)}_e$ est primitive récursive (donc $e\in N$) et pourtant $\psi^{(1)}_e$ n'est pas définie (donc $e\not\in M$). @@ -773,7 +773,7 @@ donnée d'un état parmi au plus $m$, d'une position de la tête parmi au plus $p(n)$ (puisque la tête visite au plus ce nombre de cellules), et de la valeur de chaque cellule du ruban ; or au plus $p(n)+n$ cellules peuvent contenir un $1$ (à n'importe quel moment de l'exécution), car -la tête n'en viiste qu'au plus $p(n)$ et au plus $n$ portent un $1$ +la tête n'en visite qu'au plus $p(n)$ et au plus $n$ portent un $1$ initialement : il y a donc au plus $2^{p(n)+n}$ configurations possibles du ruban, et au plus $m\times p(n)\times 2^{p(n)+n}$ configurations de l'ensemble de la machine. @@ -787,11 +787,10 @@ distinctes, donc termine en au plus $m\times p(n)\times 2^{p(n)+n}$ étapes. \textbf{(3)} On vient de montrer que le calcul de $f$ par -$\mathscr{M}$ es fait en temps au plus $m\times p(n)\times -2^{p(n)+n}$. Mais ceci est une fonction p.r. de $n$ (car $p$ l'est, -et que $k \mapsto 2^k$ l'est, et que $m$ est une constante ici). Donc -$f$ est calculée en complexité en temps p.r., donc elle est elle-même -p.r. +$\mathscr{M}$ fait en temps au plus $m\times p(n)\times 2^{p(n)+n}$. +Mais ceci est une fonction p.r. de $n$ (car $p$ l'est, et que $k +\mapsto 2^k$ l'est, et que $m$ est une constante ici). Donc $f$ est +calculée en complexité en temps p.r., donc elle est elle-même p.r. \end{corrige} % |