Calculabilité
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (Une décennie est égale à dix ans. Le terme dérive des mots latins de decem « dix » et annus « année.) 1930 afin de répondre à des problèmes fondamentaux de logique mathématique (La logique mathématique est née à la fin du XIXe siècle de la logique au sens philosophique du terme. Ses débuts furent marqués par la rencontre...), dont celui énoncé par David Hilbert et appelé Entscheidung Problem ou Problème de la décision (En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du...). 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 calculcable 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 (Une fonction calculable (ou fonction récursive) est une fonction semi-calculable (ou fonction partielle récursive) qui est aussi totale, c'est-à-dire définie pour toute entrée (en tout point). Ce...)?

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 (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) 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 (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie...), 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 (Le lambda-calcul (ou λ-calcul) est un langage de programmation théorique inventé par Alonzo Church dans les années 1930. Ce langage a été le premier utilisé pour définir et caractériser les fonctions...)
  • 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 (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est l'affirmation ou la prise de position d'un locuteur, à l'égard du sujet ou du thème qu'il évoque.) Church-Turing.

Page générée en 0.053 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique