Calculabilité

Infos
La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la notion intuitive de fonction calculable est aussi vieille que les mathématiques (voir l'article Histoire des mathématiques), la formalisation de ces notions a commencé dans la décennie 1930 afin de répondre à des problèmes fondamentaux de logique mathématique, dont celui énoncé p
Calculabilité

La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la notion intuitive de fonction calculable est aussi vieille que les mathématiques (voir l'article Histoire des mathématiques), la formalisation de ces notions a commencé dans la décennie 1930 afin de répondre à des problèmes fondamentaux de logique mathématique, dont celui énoncé par David Hilbert et appelé Entscheidung Problem ou Problème de la décision. La calculabilité 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 calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.

Qu'est-ce qu'une fonction calculable?

Existence de fonctions non calculables

Il peut être démontré qu'il existe des fonctions f qui sont incalculables, c’est-à-dire qu'il n'existe aucun algorithme qui, étant donné x, retourne toujours la valeur f(x) en un temps fini. L'exemple 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. Un autre exemple d'une fonction non calculable, plus perturbante dans un certain sens, est celle dite du castor affairé (voir l'article en anglais busy beaver). Il s'agit d'une fonction bien définie, ayant des valeurs pour chaque entier, mais dont on ne peut pas calculer la valeur. Plusieurs modèles de calcul sont utilisés en calculabilité:
- machines de Turing
- machine à compteurs
- lambda-calcul
- automates cellulaires
- fonctions récursives
- RAM
- PRAM Malgré la diversité de ces modèles, la classe de fonctions calculables par chacun de ceux-ci est unique et cette constatation mène à la thèse Church-Turing.

Voir aussi

- Ensemble récursif
- Récursivement énumérable
- Hiérarchie arithmétique
- Thèse de Church-Turing Voir aussi Théorème de récursion de Kleene. Catégorie:Calculabilité Catégorie:Logique mathématique ar:نظرية الحسوبية cs:Teorie vyčíslitelnosti de:Berechenbarkeitstheorie en:Computability theory (computer science) es:Teoría de la computabilidad fa:نظریه محاسبه‌پذیری he:חישוביות hr:Teorija izračunljivosti (računarstvo) it:Teoria della calcolabilità ja:計算可能性理論 ko:계산 가능성 이론 nl:Berekenbaarheid pl:Teoria obliczalności pt:Computabilidade ru:Теория вычислимости simple:Computability theory th:ทฤษฎีการคำนวณได้
Sujets connexes
Algorithmique   Automate cellulaire   Castor affairé   David Hilbert   Ensemble récursif   Fonction (informatique)   Fonction calculable   Fonction récursive   Histoire des mathématiques   Hiérarchie arithmétique   Informatique théorique   Lambda-calcul   Logique mathématique   Machine de Turing   Machine à compteurs   Parallel random access machine   Problème de l'arrêt   Problème de la décision   Récursivement énumérable   Théorème de récursion de Kleene  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^