Scribd
Importer
430 vues11 pages

Chapitre 1

Ce chapitre introduit les notions de calculabilité et de décidabilité en logique mathématique et en informatique théorique. Il détaille ces deux notions et explique ce qu'est une fonction calculable selon plusieurs définitions équivalentes comme les fonctions récursives ou les machines de Turing. Il présente également des fonctions incalculables et le problème indécidable de l'arrêt. La décidabilité concerne la possibilité de répondre par oui ou non à une question posée de manière algorithmique et logique.

Transféré par

Alimi Tahar
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PPTX, PDF, TXT ou lisez en ligne sur Scribd
430 vues11 pages

Chapitre 1

Ce chapitre introduit les notions de calculabilité et de décidabilité en logique mathématique et en informatique théorique. Il détaille ces deux notions et explique ce qu'est une fonction calculable selon plusieurs définitions équivalentes comme les fonctions récursives ou les machines de Turing. Il présente également des fonctions incalculables et le problème indécidable de l'arrêt. La décidabilité concerne la possibilité de répondre par oui ou non à une question posée de manière algorithmique et logique.

Transféré par

Alimi Tahar
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PPTX, PDF, TXT ou lisez en ligne sur Scribd

Chapitre 1

Introduction générale
La théorie de la calculabilité et décidabilité est un domaine
de la logique mathématique et de l’informatique théorique.
Dans ce qui suit, ces deux notions vont être détaillées.
1. Calculabilité
La calculabilité cherche d'une part à identifier la classe des
fonctions qui peuvent être calculées à l'aide d'un
algorithme  et d'autre part à appliquer ces concepts à des
questions fondamentales des  mathématiques.
Une bonne appréhension de ce qui est calculable et de ce
qui ne l'est pas permet de voir les limites des problèmes
que peuvent résoudre les ordinateurs.
Mais la notion de calculabilité ne se limite pas aux
fonctions. On peut parler également de nombres
calculables  (réels ou complexes).
Intuitivement, une fonction f est une fonction calculable
s'il existe une méthode précise qui, étant donné un
argument x, permet d'obtenir l'image f(x) en un nombre
fini d'étapes.
Plusieurs formalisations mathématiques de ce que peut
être une méthode de calcul existent et on peut montrer
qu'un grand nombre d'entre elles (fonctions récursives,
machine de Turing, lambda calcul, …) sont
équivalentes, c'est-à-dire qu'elles définissent
exactement les mêmes fonctions calculables.
Formellement, une fonction calculable est donc une
fonction calculable selon l'une de ces définitions, par
exemple le lambda-calcul. La thèse de Church énonce que
les définitions mathématiques équivalentes ci-dessus
capturent bien le concept intuitif de méthode de calcul
fonctionnant en temps fini.
Il peut être démontré qu'il existe des fonctions f qui
sont incalculables, c’est-à-dire dont, étant donné x, la
valeur f(x) ne peut être calculée en un temps fini par
aucun algorithme que l'on aurait associé à f.
On connaît de nombreux exemples explicites de fonctions
incalculables. Le plus courant est celui du problème de
l’arrêt : il n'existe pas de programme universel qui prenne
n'importe quel programme en argument et qui, en temps
fini, renvoie «oui» si l'exécution du programme reçu en
argument finit par s'arrêter et «non» s'il ne finit pas.
2. Décidabilité
En logique mathématique, le terme décidabilité recouvre
deux concepts liés : la décidabilité logique et la décidabilité
algorithmique.
L’indécidabilité est la négation de la décidabilité. Dans les
deux cas, il s'agit de formaliser l'idée qu'on ne peut pas
toujours conclure lorsque l'on se pose une question, même si
celle-ci est sous forme logique.
Un problème de décision est dit décidable s'il existe un
algorithme qui se termine en un nombre fini d'étapes, qui le
décide, c'est-à-dire qui réponde par oui ou par non à la question
posée par le problème. S'il n'existe pas de tels algorithmes, le
problème est dit indécidable. Par exemple, le problème de
l’arrêt est indécidable. On peut formaliser la notion de fonction
calculable par algorithme, de diverses façons, par exemple en
utilisant les machine de Turing.
Si aucun algorithme ne peut répondre à la question, on peut
parler d’indécidabilité algorithmique.
Une petite mise au point est peut-être nécessaire : Dire qu'un
problème est indécidable ne veut pas dire que la question posée
n'a pas et n'aura jamais de solution, mais seulement qu'il
n'existe pas de méthode unique et bien définie, applicable d'une
façon mécanique, pour répondre à la question.

Vous aimerez peut-être aussi