Théorie de la calculabilité

Théorie de la calculabilité

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 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.

Sommaire

Qu'est-ce qu'une fonction calculable?

Une fonction calculable est une fonction qui peut-être définie par un algorithme. Cette définition intuitive a besoin d'être précisée en donnant une définition précise, par exemple, en disant qu'un algorithme est défini par une expression du lambda-calcul[1]. La thèse de Church énonce que la définition intuitive et la définition mathématique rigoureuse coïncident. De fait, on a pu montrer que toutes les définitions mathématiques (fonctions récursives, machine de Turing, lambda-calcul, machine à compteurs, automate cellulaire, etc.) sont équivalentes.

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. En effet, chaque algorithme calcule au plus une fonction et il y a un nombre dénombrable d'algorithmes (un algorithme peut toujours être représenté par un mot fini sur un alphabet fini), donc il y a seulement un nombre dénombrable de fonctions calculables. En revanche, les fonctions (partielles ou pas) sur un domaine infini ne sont pas dénombrables. Ceci fournit une preuve de l'existence de fonctions incalculables.

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. Un autre exemple d'une fonction non calculable, plus perturbante dans un certain sens, est celle dite du castor affairé. Il s'agit d'une fonction bien définie, ayant des valeurs pour chaque entier, mais dont on ne peut pas calculer la valeur. Grégory Chaitin a introduit un nombre Ω qui a, entre autres, la particularité d'être parfaitement défini, mais dont la suite des décimales ne peut pas être donnée par une fonction calculable.

Modèles de calcul

Plusieurs modèles de calcul sont utilisés en calculabilité :

Malgré la diversité de ces modèles, la classe de fonctions calculables par chacun de ceux-ci est unique et cette constatation est le fondement de la thèse de Church.

Notes

  1. Historiquement, la première caractérisation formelle et mathématique des algorithmes.

Références

  • (fr) O. Carton, Langages formels, calculabilité et complexité. Vuibert 2008, (ISBN 978-2-7117-2077-4)
  • (fr) J.-M. Autebert, Calculabilité et décidabilité. Dunod 1992, (ISBN 978-2225826320)
  • (fr) P. Wolper. Introduction à la calculabilité. 3-ième édition, Dunod 2006, (ISBN 978-2100499816)

Voir aussi

Wiktprintable without text.svg

Voir « calculabilité » sur le Wiktionnaire.

  • Portail de l’informatique Portail de l’informatique
  • Portail de la logique Portail de la logique
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Calculabilit%C3%A9 ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorie de la calculabilité de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Calculabilite — 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 …   Wikipédia en Français

  • Théorie de la récursion — 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 …   Wikipédia en Français

  • Theorie axiomatique — Théorie axiomatique Quand on parle de théorie mathématique on fait référence à une somme d énoncés, de définitions, de méthodes de preuve etc. Par exemple, quand dans cet article on parle de théorie de la calculabilité c est en ce sens. Par… …   Wikipédia en Français

  • Theorie de la complexite — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Theorie de la complexite algorithmique — Théorie algorithmique de l information La Théorie algorithmique de l information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d un ensemble de données, en utilisant… …   Wikipédia en Français

  • Théorie de la complexité algorithmique — Théorie algorithmique de l information La Théorie algorithmique de l information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d un ensemble de données, en utilisant… …   Wikipédia en Français

  • Theorie des graphes — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Theorie des types — Théorie des types La théorie des types est une branche de la logique mathématique qui a pour principales caractéristiques que tout objet (terme, fonction, ensemble) y a un type et que les entités ne peuvent se combiner qu en respectant des règles …   Wikipédia en Français

  • Theorie des langages — Théorie des langages La théorie des langages a pour objectif de comprendre le fonctionnement des langages, vus comme moyen de communication, d un point de vue mathématique. Un langage est un ensemble de mots. Un mot (ou lexème) est une… …   Wikipédia en Français

  • Théorie des langages et automates — Théorie des langages La théorie des langages a pour objectif de comprendre le fonctionnement des langages, vus comme moyen de communication, d un point de vue mathématique. Un langage est un ensemble de mots. Un mot (ou lexème) est une… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”