13.3 Machines de Turing et fonctions r´ ecursives
421
aimant, et on jette le reste du contenu de l’´ eprouvette, soit les mol´ ecules qui repr´ esentent
des chemins ne passant pas par le sommet 1. On enl` eve alors l’aimant et on ajoute un
solvant dans l´ eprouvette. On chauffe le liquide contenant les mol´ ecules passant par le
sommet 1, ce qui les d´ etache des billes de fer (celles-ci peuvent alors ˆ etre retir´ ees ` a l’aide
d’un aimant). On r´ ep´ ete les ´ etapes pr´ ec´ edentes pour les quatre autres sommets 2, 3, 4,
5.
´
Etape 4 On regarde s’il reste des chaˆ ınes d’ADN dans l’´ eprouvette : si oui, on a trouv´ e
une (ou des) solution(s) au probl` eme du chemin hamiltonien ; si non, le probl` eme n’a
probablement pas de solution.
´
Etape 5 S’il reste des chaˆ ınes, il faut les analyser pour connaˆ ıtre le ou les chemins.
Adleman a pass´ e sept jours dans son laboratoire pour trouver la solution du graphe
hamiltonien de la figure 13.1 par cette m´ ethode.
13.3 Machines de Turing et fonctions r´ ecursives
Comme nous l’avons dit dans l’introduction, lorsqu’on ´ etudie le potentiel de calcul
th´ eorique d’un ordinateur, une des bases de r´ ef´ erence les plus utilis´ ees est la machine
de Turing. Celle-ci a ´ et´ e invent´ ee par Alan Turing en 1936 [9] dans le but de d´ efinir la
notion d’algorithme.
Dans cette section, nous aborderons le fonctionnement d’une machine de Turing
standard. Nous ´ etablirons ensuite le lien entre ce type de machine, les fonctions primitives r´ ecursives et les fonctions r´ ecursives. Nous conclurons par une pr´ esentation de la
th` ese de Church, qui est souvent consid´ er´ ee comme la d´ efinition d’un algorithme.
13.3.1 Le fonctionnement d’une machine de Turing
Il est int´ eressant de comparer une machine de Turing `
a un programme d’ordinateur.
La machine de Turing est faite d’un ruban infini qui peut ˆ etre consid´ er´ e comme la
m´ emoire d’un ordinateur (qui, elle, est limit´ ee). Le ruban est s´ epar´ e en cases distinctes,
chacune pouvant contenir au plus un symbole. En tout temps, seul un nombre fini de
cases contiennent un symbole diff´ erent du symbole blanc. La machine travaille sur une
case ` a la fois. La case sur laquelle elle travaille est identifi´ ee par un pointeur. L’op´ eration
qui a lieu sur le ruban d´ epend d’une fonction ϕ qui se compare au programme d’un
ordinateur. Cette fonction prend pour entr´ ee le symbole point´ e et l’´ etat du pointeur. Cet
´ etat repr´ esente le degr´ e d’avancement du programme. Tout comme en programmation,
la fonction ϕ doit respecter des r` egles de syntaxe particuli` eres et d´ epend du probl` eme
qui doit ˆ etre r´ esolu.
D´ ebutons cette section par l’´ etude d’un exemple dans lequel nous construirons une
machine de Turing pour un probl` eme particulier. Par la suite, nous d´ efinirons de fa¸ con
plus formelle ce qu’est une machine de Turing.
421
aimant, et on jette le reste du contenu de l’´ eprouvette, soit les mol´ ecules qui repr´ esentent
des chemins ne passant pas par le sommet 1. On enl` eve alors l’aimant et on ajoute un
solvant dans l´ eprouvette. On chauffe le liquide contenant les mol´ ecules passant par le
sommet 1, ce qui les d´ etache des billes de fer (celles-ci peuvent alors ˆ etre retir´ ees ` a l’aide
d’un aimant). On r´ ep´ ete les ´ etapes pr´ ec´ edentes pour les quatre autres sommets 2, 3, 4,
5.
´
Etape 4 On regarde s’il reste des chaˆ ınes d’ADN dans l’´ eprouvette : si oui, on a trouv´ e
une (ou des) solution(s) au probl` eme du chemin hamiltonien ; si non, le probl` eme n’a
probablement pas de solution.
´
Etape 5 S’il reste des chaˆ ınes, il faut les analyser pour connaˆ ıtre le ou les chemins.
Adleman a pass´ e sept jours dans son laboratoire pour trouver la solution du graphe
hamiltonien de la figure 13.1 par cette m´ ethode.
13.3 Machines de Turing et fonctions r´ ecursives
Comme nous l’avons dit dans l’introduction, lorsqu’on ´ etudie le potentiel de calcul
th´ eorique d’un ordinateur, une des bases de r´ ef´ erence les plus utilis´ ees est la machine
de Turing. Celle-ci a ´ et´ e invent´ ee par Alan Turing en 1936 [9] dans le but de d´ efinir la
notion d’algorithme.
Dans cette section, nous aborderons le fonctionnement d’une machine de Turing
standard. Nous ´ etablirons ensuite le lien entre ce type de machine, les fonctions primitives r´ ecursives et les fonctions r´ ecursives. Nous conclurons par une pr´ esentation de la
th` ese de Church, qui est souvent consid´ er´ ee comme la d´ efinition d’un algorithme.
13.3.1 Le fonctionnement d’une machine de Turing
Il est int´ eressant de comparer une machine de Turing `
a un programme d’ordinateur.
La machine de Turing est faite d’un ruban infini qui peut ˆ etre consid´ er´ e comme la
m´ emoire d’un ordinateur (qui, elle, est limit´ ee). Le ruban est s´ epar´ e en cases distinctes,
chacune pouvant contenir au plus un symbole. En tout temps, seul un nombre fini de
cases contiennent un symbole diff´ erent du symbole blanc. La machine travaille sur une
case ` a la fois. La case sur laquelle elle travaille est identifi´ ee par un pointeur. L’op´ eration
qui a lieu sur le ruban d´ epend d’une fonction ϕ qui se compare au programme d’un
ordinateur. Cette fonction prend pour entr´ ee le symbole point´ e et l’´ etat du pointeur. Cet
´ etat repr´ esente le degr´ e d’avancement du programme. Tout comme en programmation,
la fonction ϕ doit respecter des r` egles de syntaxe particuli` eres et d´ epend du probl` eme
qui doit ˆ etre r´ esolu.
D´ ebutons cette section par l’´ etude d’un exemple dans lequel nous construirons une
machine de Turing pour un probl` eme particulier. Par la suite, nous d´ efinirons de fa¸ con
plus formelle ce qu’est une machine de Turing.