H.
Yedjour
1- Calculabilité
La calculabilité (ou récursivité) cherche d'une part à identifier la classe des fonctions qui
peuvent être calculées à l'aide d'un algorithme et à appliquer ces concepts à des questions
fondamentales des mathématiques. Une bonne appréhension de ce qui est calculcable et de ce
qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs .
Parmi les modèles de calcul utilisés en calculabilité, on peut citer les machines de Turing.
Dans le chapitre dans lequel on a décrit la machine de Turing avec des exemples simples qu’on
a résolus ; on peut penser que seuls les programmes simples peuvent être exécutés par la
machine de Turing, en fait, c’est faux.
La thèse de Church/Turing stipule la chose suivante : Pour tout problème pour lequel il existe
un algorithme qui résoud ce probléme P, alors il existe une machine de turing qui résoud le
probléme P.
∀ ∃ é ( ) ∃ é ()
Grâce à cette thèse, la notion de calculabilité ou récursivité possède désormais une signification
précise.
Calculable, signifie qu’il existe un algorithme au sens de la machine de Turing. Même la
notion d’algorithme pour la première fois dans l’histoire des maths a une signification.
Un algorithme est une table de transition au sens de la machine de Turing.
Une définition simple est la suivante : une fonction f est calculable s’il existe un algorithme pour la
calculer. Parmi les généralisation possibles de la machine Turing, il existe une machine
particulièrement intéressante : machine U.
L’idée est la même, quand on veut exécuter un programme on va passer comme paramètres
pour la machine U, d’abord la table de transition, ensuite le nombre en entrée (ou en lecture :
voir exemple incrementer(n)). Ainsi, l’entrée à la machine U est une table de transition et un
élément. La thèse de Church/Turing devient encore plus simple :
∀ ∃ é ( ) é ()
On vient de voir les principaux fondamentaux des ordinateurs d’aujourd’hui :
• La notion de registre Etat
• La notion de configuration tête de lecture
• La notion de programme table de transition qu’on passe comme paramètre
• Cycle d’instruction (ce qu’on exécute à un instant donné) déplacement case par case
Tous ces éléments sont les fondements des ordinateurs d’aujourd’hui et se sont aussi les
fondements de l’informatique théorique : calculabilité, décidabilité, complexité.
[Link]
2- Décidabilité
Un problème P est dit décidable s'il existe un algorithme A, une procédure qui termine en un
nombre fini d'étapes, qui le décide, c'est-à-dire qui réponde par oui (ou vrai) ou par non(ou
faux) à la question posée par le problème. S'il n'existe pas de tels algorithmes, le problème est
dit indécidable.
Decidabilité(P) ∃A/ A résoud (P)
Exemple : le probléme qui permet de savoir si le nombre est pair ou pas est décidable. Pourquoi ;
parcequ’il est facile de présenter un algorithme qu’on appelle Apair(x), qui pour chaque
élément x, permet de savoir s’il est pair ou pas. On suppose que la fonction Apair est de type
booléenne (puisqu’on parle de la logique ; (dans la logique mathématique on démontre pour
aboutir à vrai ou faux))
Parité(x) Apair(x) ∈
∈
[Link]
3- Récursivité et problème d’arrêt
Certaines informations sont spécifiques au monde mathématique (c.à.d qu’on ne peut pas
les résoudre par un simple algorithme). En effet, Alain turing était le premier à montrer qu’une
suite peut être mathématiquement parfaitement définie et pourtant non calculable par
programme. Pour cela, il considère le problème d’arrêt d’un programme (ou pb d’arrêt d’une
machine de Turing, ce qui revient au même).
Etant donné un programme, peut-on savoir si, une fois démarré, il finira par s’arrêter, ou s’il
tournera indéfiniment ? la réponse est non. Aucun programme ne peut exister pour cela.
Exemple :
Prenant l’ensemble dénombrable de tous les programmes. Soit S la suite de ‘0’ et de ‘1’ ;
S=(a0,a1,a2….) définie par :
ai=1, si le programme i s’arrête
ai=0, sinon
Cette suite S est non calculable par programme (pourtant mathématiquement c’est démontré).
Pendant très longtemps, les mathématiciens pensaient que tout problème mathématique était
décidable (bien qu’ils n’ont pas trouvé des algorithmes pour tous les problémes mathématiques,
mais ils pensaient qu’ils allaient en trouver.
Il a fallu qu’en 1936, Alain Turing dans sa thèse dans laquelle il décrit la machine Turing, dans
laquelle la notion d’algorithme pouvait être décrite de manière simple ; il montra aussi qu’il
existe un problème très simple qui était indécidable. Le contre-exemple qu’il a démontré est le
problème d’arrêt.
Pour comprendre le problème de l’arrêt, il faut savoir que les algorithmes sont de 2 natures. Il
y’a des algorithmes qui s’arrêtent ∀ l’entrée qu’on donne. Et il y’a d’autres qui ne s’arrêtent
pas. Prenant un exemple simple :
Apair(x) ∈
∈
Apair’(x) tant que Apair(x) = ∗2
Si x est pair alors il le multiplie par 2. Cet algorithme ne s’arrête jamais. Alors Apair’ ∈ arrêt.
Dans le cadre de la machine de turing, La suite des configurations dans la table de transition
ne passe jamais par un etat final et est infinie.
