Qu’est-ce que la calculabilité?

– Syndrome du “mouvement perpétuel”.

– Les limites intrinsèques de l’informatique.

– Quels problèmes sont solubles par un programme exécuté sur un ordinateur.

La notion de problème

Caractéristiques de la notion de problèmes : – générique,

– les instances du problème ont une réponses,

– le problème est indépendant de la manière de le ré-

soudre. Exemples de problèmes :

– Trier un tableau ;

– Déterminer si un programme termine quelque soit les données ;

– Déterminer si un polynôme à coefficients entiers a des racines entières.

La notion de programme

procédure effective: solution à un problème qui à la forme d’un programme pouvant être exécuté sur un ordinateur.

Solution au problème de l’arrêt : déterminer si le programme n’a pas de boucles ou de séquences d’appels récursifs infinies.

function mystere (n: entier) : entier begin

if (n = 1)

then 1

else if (pair n) then mystere(n/2) else mystere(3*n+1)

end;

Programme = automate

Représentation des problèmes

Nécessité d’une fonction d’encodage. def.: Un alphabet est un ensemble fini de symboles. def.: Un mot est une séquence finie de symboles (ε est le mot vide). Soit un problème encodé sur un alphabet. L’ensemble des mots est partitionné en deux :

– instances positives : la réponse est oui pour ce mot,

– instances négatives : ce mot n’encode pas un problème ou la réponse est non pour ce mot.

Représentation et langages

Un problème est caractérisé par l’ensemble des mots qui sont ses instances positives. def.: Un langage est un ensemble de mots définis sur le même alphabet. Équivalence entre résoudre un problème et reconnaître le langage des encodages des instances positives du problème. Th.: L’ensemble des sous-ensembles d’un ensemble dénombrable n’est pas dénombrable. Cor.: L’ensemble des langages n’est pas dénombrable.