diff options
| -rw-r--r-- | notes-inf105.tex | 65 |
1 files changed, 38 insertions, 27 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 0e3b388..1ac129e 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -6456,7 +6456,8 @@ d'un tel $k$). suivant : tout ensemble semi-décidable infini a un sous-ensemble décidable infini (indication : prendre une fonction qui énumère l'ensemble et jeter toute valeur qui n'est pas strictement plus - grande que toutes les précédentes).\par} + grande que toutes les précédentes). + Cf. exercice \ref{decidable-iff-image-of-computable-increasing}.\par} \subsection{Machine universelle, et problème de l'arrêt} @@ -6478,36 +6479,46 @@ sont pas importants\footnote{Par exemple, ceux qui aiment le langage ce programme est valable (remplacer Java par tout autre langage préféré).}. +On aura tendance, dans la suite, à écrire « le $e$-ième algorithme », +voire « l'algorithme $e$ » (ou « le programme $e$ »), pour désigner +l'algorithme codé par l'entier naturel $e$ (c'est-à-dire qu'on +identifie librement un programme et son codage de Gödel) : on peut +donc écrire que $\varphi_e(n)$ est le résultat de l'exécution du +programme $e$ quand on lui fournit $n$ en entrée (ou non défini si +cette exécution ne termine pas). + \medskip -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$ -si et seulement si $T$ termine sur l'entrée $n$, et, dans ce cas, -renvoie la même valeur). +Un point crucial dans cette numérotation des algorithmes par des +entiers naturels $e$ 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$ si et seulement si $T$ termine +sur l'entrée $n$, et, dans ce cas, renvoie la même valeur). Autrement +dit, le calcul de $\varphi_e(n)$ en fonction de $e$ et $n$ est +lui-même algorithmique. \smallskip -Informatiquement, ceci représente le fait que les programmes -informatiques sont eux-mêmes représentables informatiquement : dans un -langage de programmation Turing-complet, on peut écrire un -\emph{interpréteur} pour le langage lui-même (ou pour un autre langage -Turing-complet), c'est-à-dire un programme qui prend en entrée la -représentation $e$ d'un autre programme et qui exécute ce programme -(sur une entrée $n$). - -Mathématiquement, on peut le formuler comme le fait que la fonction -(partielle) $(e,n) \mapsto \varphi_e(n)$ (= résultat du $e$-ième -algorithme appliqué sur l'entrée $n$) est elle-même calculable -partielle. - -Philosophiquement, cela signifie que la notion d'exécution d'un -algorithme est elle-même algorithmique : on peut écrire un algorithme -qui, donnée une description (formelle !) d'un algorithme et une entrée -à laquelle l'appliquer, effectue l'exécution de l'algorithme fourni -sur l'entrée fournie. +\underline{Informatiquement}, ceci représente le fait que les +programmes informatiques sont eux-mêmes représentables +informatiquement : dans un langage de programmation Turing-complet, on +peut écrire un \emph{interpréteur} $U$ pour le langage lui-même (ou +pour un autre langage Turing-complet), c'est-à-dire un programme qui +prend en entrée la représentation $e$ d'un autre programme et qui +exécute ce programme (sur une entrée $n$). + +\underline{Mathématiquement}, on peut le formuler comme le fait que la +fonction (partielle) $(e,n) \mapsto \varphi_e(n)$ (= résultat du +$e$-ième algorithme appliqué sur l'entrée $n$) est elle-même +calculable partielle. + +\underline{Philosophiquement}, cela signifie que la notion d'exécution +d'un algorithme est elle-même algorithmique : on peut écrire un +algorithme qui, donnée une description (formelle !) d'un algorithme et +une entrée à laquelle l'appliquer, effectue l'exécution de +l'algorithme fourni sur l'entrée fournie. \smallskip @@ -9054,7 +9065,7 @@ prouve (1). % -\exercice +\exercice\label{decidable-iff-image-of-computable-increasing} Soit $A \subseteq \mathbb{N}$ un ensemble infini. Montrer qu'il y a équivalence entre : |