Fonction calculable - Computable function

Les fonctions calculables sont les objets d'étude de base de la théorie de la calculabilité . Les fonctions calculables sont l'analogue formalisé de la notion intuitive d' algorithmes , en ce sens qu'une fonction est calculable s'il existe un algorithme qui peut faire le travail de la fonction, c'est-à-dire qu'étant donné une entrée du domaine de la fonction, il peut renvoyer la sortie correspondante. Les fonctions calculables sont utilisées pour discuter de la calculabilité sans faire référence à un modèle concret de calcul tel que les machines de Turing ou les machines à registres . Toute définition, cependant, doit faire référence à un modèle de calcul spécifique, mais toutes les définitions valides donnent la même classe de fonctions. Les modèles particuliers de calculabilité qui donnent lieu à l'ensemble des fonctions calculables sont les fonctions calculables de Turing et les fonctions récursives générales .

Avant la définition précise de fonction calculable, les mathématiciens utilisaient souvent le terme informel effectivement calculable . Ce terme a depuis été identifié aux fonctions calculables. Notez que la calculabilité effective de ces fonctions n'implique pas qu'elles puissent être calculées efficacement (c'est-à-dire calculées dans un laps de temps raisonnable). En fait, pour certaines fonctions effectivement calculables, on peut montrer que tout algorithme qui les calcule sera très inefficace dans le sens où le temps d'exécution de l'algorithme augmente de manière exponentielle (voire superexponentielle ) avec la longueur de l'entrée. Les domaines de calculabilité réalisable et de complexité computationnelle étudient des fonctions qui peuvent être calculées efficacement.

Selon la thèse de Church-Turing , les fonctions calculables sont exactement les fonctions qui peuvent être calculées à l'aide d'un appareil de calcul mécanique avec un temps et un espace de stockage illimités. De manière équivalente, cette thèse affirme qu'une fonction est calculable si et seulement si elle possède un algorithme. Notez qu'un algorithme dans ce sens est compris comme une séquence d'étapes qu'une personne avec un temps illimité et une quantité illimitée de stylo et de papier pourrait suivre.

Les axiomes de Blum peuvent être utilisés pour définir une théorie abstraite de la complexité computationnelle sur l'ensemble des fonctions calculables. Dans la théorie de la complexité computationnelle, le problème de la détermination de la complexité d'une fonction calculable est connu sous le nom de problème de fonction .

Définition

La calculabilité d'une fonction est une notion informelle. Une façon de le décrire est de dire qu'une fonction est calculable si sa valeur peut être obtenue par une procédure efficace . Avec plus de rigueur, une fonction est calculable si et seulement s'il existe une procédure efficace qui, étant donné n'importe quel k - uplet de nombres naturels, produira la valeur . En accord avec cette définition, le reste de cet article suppose que les fonctions calculables prennent un nombre fini de nombres naturels comme arguments et produisent une valeur qui est un seul nombre naturel. ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ ${\displaystyle \mathbf {x} }$${\displaystyle f(\mathbf {x} )}$

En contrepartie de cette description informelle, il existe de multiples définitions mathématiques formelles. La classe des fonctions calculables peut être définie dans de nombreux modèles de calcul équivalents , y compris

• Machines de Turing
• fonctions μ-récursives
• Calcul lambda
• Machines à poster (Machines à post-Turing et machines à étiquettes ).
• Enregistrer les machines

Bien que ces modèles utilisent des représentations différentes pour les fonctions, leurs entrées et leurs sorties, des traductions existent entre deux modèles, et donc chaque modèle décrit essentiellement la même classe de fonctions, donnant lieu à l'opinion que la calculabilité formelle est à la fois naturelle et pas trop étroite .

Par exemple, on peut formaliser les fonctions calculables en tant que fonctions μ-récursives , qui sont des fonctions partielles qui prennent des tuples finis de nombres naturels et renvoient un seul nombre naturel (comme ci-dessus). Il s'agit de la plus petite classe de fonctions partielles qui comprend les fonctions constante, successeur et de projection, et est fermée par composition , récursivité primitive et l' opérateur .

De manière équivalente, les fonctions calculables peuvent être formalisées comme des fonctions qui peuvent être calculées par un agent de calcul idéalisé tel qu'une machine de Turing ou une machine à registres . Formellement parlant, une fonction partielle peut être calculée si et seulement s'il existe un programme informatique ayant les propriétés suivantes : ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$

1. Si est défini, alors le programme se terminera sur l'entrée avec la valeur stockée dans la mémoire de l'ordinateur.${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x} }$${\displaystyle f(\mathbf {x} )}$
2. Si est indéfini, alors le programme ne se termine jamais sur l'entrée .${\displaystyle f(\mathbf {x} )}$${\displaystyle \mathbf {x} }$

Caractéristiques des fonctions calculables

La caractéristique de base d'une fonction calculable est qu'il doit y avoir une procédure finie (un algorithme ) indiquant comment calculer la fonction. Les modèles de calcul énumérés ci-dessus donnent différentes interprétations de ce qu'est une procédure et de la façon dont elle est utilisée, mais ces interprétations partagent de nombreuses propriétés. Le fait que ces modèles donnent des classes équivalentes de fonctions calculables provient du fait que chaque modèle est capable de lire et d'imiter une procédure pour n'importe lequel des autres modèles, tout comme un compilateur est capable de lire des instructions dans un langage informatique et d'émettre des instructions dans une autre langue.

Enderton [1977] donne les caractéristiques suivantes d'une procédure de calcul d'une fonction calculable ; des caractérisations similaires ont été données par Turing [1936], Rogers [1967] et d'autres.

• "Il doit y avoir des instructions exactes (c'est-à-dire un programme), de longueur finie, pour la procédure." Ainsi, chaque fonction calculable doit avoir un programme fini qui décrit complètement comment la fonction doit être calculée. Il est possible de calculer la fonction en suivant simplement les instructions ; aucune devinette ou perspicacité particulière n'est requise.
• "Si la procédure reçoit un k -uplet x dans le domaine de f , alors après un nombre fini d'étapes discrètes, la procédure doit se terminer et produire f( x ) ." Intuitivement, la procédure se déroule étape par étape, avec une règle spécifique pour couvrir ce qu'il faut faire à chaque étape du calcul. Seules un nombre fini d'étapes peuvent être effectuées avant que la valeur de la fonction ne soit renvoyée.
• "Si la procédure reçoit un k -tuple x qui n'est pas dans le domaine de f , alors la procédure peut continuer indéfiniment, sans jamais s'arrêter. Ou elle peut rester bloquée à un moment donné (c'est-à-dire qu'une de ses instructions ne peut pas être exécutée) , mais il ne doit pas prétendre produire une valeur pour f en x ." Ainsi, si une valeur pour f( x ) est trouvée, ce doit être la valeur correcte. Il n'est pas nécessaire pour l'agent de calcul de distinguer les résultats corrects des résultats incorrects car la procédure est définie comme correcte si et seulement si elle produit un résultat.

Enderton poursuit en énumérant plusieurs clarifications de ces 3 exigences de la procédure pour une fonction calculable :

1. La procédure doit théoriquement fonctionner pour des arguments arbitrairement volumineux. On ne suppose pas que les arguments soient inférieurs au nombre d'atomes de la Terre, par exemple.
2. La procédure doit s'arrêter après un nombre fini d'étapes afin de produire une sortie, mais elle peut prendre arbitrairement de nombreuses étapes avant de s'arrêter. Aucune limitation de temps n'est supposée.
3. Bien que la procédure puisse utiliser uniquement une quantité finie d'espace de stockage lors d'un calcul réussi, il n'y a pas de limite sur la quantité d'espace utilisée. On suppose qu'un espace de stockage supplémentaire peut être accordé à la procédure chaque fois que la procédure le demande.

Pour résumer, sur la base de cette vue, une fonction est calculable si : (a) étant donné une entrée de son domaine, s'appuyant éventuellement sur un espace de stockage illimité, elle peut donner la sortie correspondante en suivant une procédure (programme, algorithme) qui est formée par un nombre fini d'instructions exactes et non ambiguës ; (b) il renvoie une telle sortie (s'arrête) en un nombre fini d'étapes ; et (c) si on lui donne une entrée qui n'est pas dans son domaine, elle ne s'arrête jamais ou reste bloquée.

Le domaine de la complexité computationnelle étudie les fonctions avec des limites prescrites sur le temps et/ou l'espace autorisé dans un calcul réussi.

Ensembles et relations calculables

Un ensemble A d'entiers naturels est dit calculable (synonymes : récursif , décidable ) s'il existe une fonction totale calculable f telle que pour tout nombre naturel n , f ( n ) = 1 si n est dans A et f ( n ) = 0 si n n'est pas dans A .

Un ensemble de nombres naturels est appelé calculable énumérable (synonymes : récursivement énumérable , semidécidable ) s'il existe une fonction calculable f telle que pour chaque nombre n , f ( n ) est défini si et seulement si n est dans l'ensemble. Ainsi, un ensemble est énumérable par calcul si et seulement si c'est le domaine d'une fonction calculable. Le mot énumérable est utilisé car les éléments suivants sont équivalents pour un sous-ensemble non vide B des nombres naturels :

• B est le domaine d'une fonction calculable.
• B est la plage d'une fonction calculable totale. Si B est infini, la fonction peut être supposée injective .

Si un ensemble B est l'étendue d'une fonction f alors la fonction peut être considérée comme une énumération de B , car la liste f (0), f (1), ... inclura chaque élément de B .

Parce que chaque relation finitaire sur les nombres naturels peut être identifiée avec un ensemble correspondant de séquences finies de nombres naturels, les notions de relation calculable et de relation calculable énumérable peuvent être définies à partir de leurs analogues pour les ensembles.

Langages formels

En théorie de la calculabilité en informatique , il est courant de considérer les langages formels . Un alphabet est un ensemble arbitraire. Un mot sur un alphabet est une séquence finie de symboles de l'alphabet ; le même symbole peut être utilisé plusieurs fois. Par exemple, les chaînes binaires sont exactement les mots de l'alphabet {0, 1} . Une langue est un sous-ensemble de l'ensemble de tous les mots d'un alphabet fixe. Par exemple, la collection de toutes les chaînes binaires qui contiennent exactement 3 uns est un langage sur l'alphabet binaire.

Une propriété clé d'une langue formelle est le niveau de difficulté requis pour décider si un mot donné est dans la langue. Un système de codage doit être développé pour permettre à une fonction calculable de prendre en entrée un mot arbitraire de la langue ; ceci est généralement considéré comme une routine. Une langue est dite calculable (synonymes : récursive , décidable ) s'il existe une fonction calculable f telle que pour chaque mot w sur l'alphabet, f ( w ) = 1 si le mot est dans la langue et f ( w ) = 0 si le mot n'est pas dans la langue. Ainsi, une langue est calculable juste au cas où il existe une procédure capable de dire correctement si des mots arbitraires se trouvent dans la langue.

Une langue est calculable énumérable (synonymes : récursivement énumérable , semi - décidable ) s'il existe une fonction calculable f telle que f ( w ) est définie si et seulement si le mot w est dans la langue. Le terme énumérable a la même étymologie que dans les ensembles de nombres naturels énumérables par calcul.

Exemples

Les fonctions suivantes sont calculables :

• Chaque fonction avec un domaine fini ; par exemple, toute séquence finie de nombres naturels.
• Chaque fonction constante f  : N ^k → N , f ( n ₁ ,... n _k ) := n .
• Addition f  : N ² → N , f ( n ₁ , n ₂ ) := n ₁ + n ₂
• Le plus grand commun diviseur de deux nombres
• Un coefficient de Bézout de deux nombres
• Le plus petit facteur premier d'un nombre

Si f et g sont calculables, puis sont donc: f + g , f * g , si f est unaire , max ( f , g ), min ( f , g ), arg max { y  ≤  f ( x )} et beaucoup plus de combinaisons. ${\displaystyle f\circ g}$

Les exemples suivants illustrent qu'une fonction peut être calculable bien qu'on ne sache pas quel algorithme la calcule.

• La fonction f telle que f ( n ) = 1 s'il y a une séquence d' au moins n cinq ans consécutifs dans le développement décimal de π , et f ( n ) = 0 sinon, est calculable. (La fonction f est soit la fonction constante 1, qui est calculable, ou bien il existe un k tel que f ( n ) = 1 si n < k , et f ( n ) = 0 si n ≥ k . Chacune de ces fonctions est calculable . On ne sait pas s'il y a des suites arbitrairement longues de cinq dans le développement décimal de π, donc nous ne savons pas laquelle de ces fonctions est f . Néanmoins, nous savons que la fonction f doit être calculable.)
• Chaque segment fini d'une séquence non calculable de nombres naturels (comme la fonction Busy Beaver Σ ) est calculable. Par exemple, pour chaque entier naturel n , il existe un algorithme qui calcule la suite finie Σ(0), (1), (2), ..., Σ( n ) — contrairement au fait qu'il n'y a pas algorithme qui calcule la -séquence entière , c'est-à-dire Σ( n ) pour tout n . Ainsi, "Print 0, 1, 4, 6, 13" est un algorithme trivial pour calculer Σ(0), Σ(1), Σ(2), Σ(3), Σ(4) ; de même, pour toute valeur donnée de n , un tel algorithme trivial existe (même s'il peut ne jamais être connu ou produit par quiconque) pour calculer Σ(0), Σ(1), Σ(2), ..., Σ( n ).

Thèse Church–Turing

La thèse de Church-Turing affirme que toute fonction calculable à partir d'une procédure possédant les trois propriétés énumérées ci - dessus est une fonction calculable. Parce que ces trois propriétés ne sont pas formellement énoncées, la thèse Church-Turing ne peut pas être prouvée. Les faits suivants sont souvent pris comme preuve pour la thèse :

• De nombreux modèles de calcul équivalents sont connus, et ils donnent tous la même définition de fonction calculable (ou une version plus faible, dans certains cas).
• Aucun modèle de calcul plus solide qui est généralement considéré comme étant effectivement calculable n'a été proposé.

La thèse de Church-Turing est parfois utilisée dans les preuves pour justifier qu'une fonction particulière est calculable en donnant une description concrète d'une procédure de calcul. Ceci est autorisé car on pense que toutes ces utilisations de la thèse peuvent être supprimées par le processus fastidieux d'écriture d'une procédure formelle pour la fonction dans un modèle de calcul.

Prouvabilité

Étant donné une fonction (ou, de manière similaire, un ensemble), on peut être intéressé non seulement si elle est calculable, mais aussi si cela peut être prouvé dans un système de preuve particulier (généralement l'arithmétique de Peano du premier ordre ). Une fonction dont on peut prouver qu'elle est calculable est appelée prouvablement totale .

L'ensemble des fonctions prouvablement totales est récursivement énumérable : on peut énumérer toutes les fonctions prouvablement totales en énumérant toutes leurs preuves correspondantes, qui prouvent leur calculabilité. Cela peut être fait en énumérant toutes les preuves du système de preuve et en ignorant celles qui ne sont pas pertinentes.

Relation avec les fonctions définies récursivement

Dans une fonction définie par une définition récursive , chaque valeur est définie par une formule de premier ordre fixe d'autres valeurs préalablement définies de la même fonction ou d'autres fonctions, qui peuvent être simplement des constantes. Un sous-ensemble de celles-ci est constitué des fonctions récursives primitives . Chacune de ces fonctions est prouvable totale : pour une telle fonction k-aire f , chaque valeur peut être calculée en suivant la définition en arrière, de manière itérative, et après un nombre fini d'itérations (comme cela peut être facilement prouvé), une constante est atteinte. ${\style d'affichage f(n_{1},n_{2}...n_{k})}$

L'inverse n'est pas vrai, car toutes les fonctions prouvablement totales ne sont pas récursives primitives. En effet, on peut énumérer toutes les fonctions récursives primitives et définir une fonction en telle que pour tout n , m : en ( n , m ) = f _n ( m ), où f _n est la n-ième fonction récursive primitive (pour k -ary , cela sera défini sur f _n ( m , m ... m )). Maintenant, g ( n ) = en ( n , n )+1 est prouvable total mais pas récursif primitif, par un argument de diagonalisation : s'il y avait eu un j tel que g = f _j , nous aurions obtenu g ( j ) = en ( j , j )+1 = f _j ( j )+1= g ( j )+1, une contradiction. (Les nombres de Gödel de toutes les fonctions récursives primitives peuvent être énumérés par une fonction récursive primitive, bien que les valeurs des fonctions récursives primitives ne le puissent pas.)

Une telle fonction, qui est prouvable totale mais pas récursive primitive, est la fonction d'Ackermann : puisqu'elle est définie récursivement, il est en effet facile de prouver sa calculabilité (Cependant, un argument de diagonalisation similaire peut également être construit pour toutes les fonctions définies par définition récursive ; ainsi, il existe des fonctions totales prouvables qui ne peuvent pas être définies récursivement).

Fonctions totales qui ne sont pas prouvables totales

Dans un système de preuve sonore , toute fonction prouvablement totale est bien totale, mais l'inverse n'est pas vrai : dans tout système de preuve du premier ordre qui est assez fort et solide (y compris l'arithmétique de Peano), on peut prouver (dans un autre système de preuve) existence de fonctions totales qui ne peuvent pas être prouvées totales dans le système de preuve.

Si les fonctions totales calculables sont énumérées via les machines de Turing qui les produisent, alors l'énoncé ci-dessus peut être montré, si le système de preuve est correct, par un argument de diagonalisation similaire à celui utilisé ci-dessus, en utilisant l'énumération des fonctions totales prouvables donnée précédemment. On utilise une machine de Turing qui énumère les preuves correspondantes, et pour chaque entrée n appels f _n ( n ) (où f _n est n ième fonction de cette énumération) en invoquant la machine de Turing qui calcule en fonction de la n-ième preuve . Une telle machine de Turing est garantie de s'arrêter si le système de preuve est solide.

Fonctions incalculables et problèmes insolubles

Chaque fonction calculable a une procédure finie donnant des instructions explicites et sans ambiguïté sur la façon de la calculer. De plus, cette procédure doit être codée dans l'alphabet fini utilisé par le modèle de calcul, de sorte qu'il n'y a qu'un nombre dénombrable de fonctions calculables. Par exemple, les fonctions peuvent être codées à l'aide d'une chaîne de bits (l'alphabet Σ = {0, 1 }).

Les nombres réels sont innombrables, donc la plupart des nombres réels ne sont pas calculables. Voir nombre calculable . L'ensemble des fonctions finitaires sur les nombres naturels est indénombrable, donc la plupart ne sont pas calculables. Des exemples concrets de telles fonctions sont Busy beaver , la complexité de Kolmogorov ou toute fonction qui génère les chiffres d'un nombre non calculable, comme la constante de Chaitin .

De même, la plupart des sous-ensembles des nombres naturels ne sont pas calculables. Le problème d'arrêt a été le premier ensemble de ce type à être construit. Le Entscheidungsproblem , proposé par David Hilbert , a demandé s'il existe une procédure efficace pour déterminer quelles déclarations mathématiques (codées comme des nombres naturels) sont vraies. Turing et Church ont montré indépendamment dans les années 1930 que cet ensemble de nombres naturels n'est pas calculable. Selon la thèse de Church-Turing, il n'existe pas de procédure efficace (avec un algorithme) qui puisse effectuer ces calculs.

Extensions de calculabilité

Calculabilité relative

La notion de calculabilité d'une fonction peut être relativisée à un ensemble arbitraire de nombres naturels A . Une fonction f est définie comme étant calculable dans A (équivalent A -calculable ou calculable par rapport à A ) lorsqu'elle satisfait la définition d'une fonction calculable avec des modifications permettant d'accéder à A en tant qu'oracle . Comme pour le concept de fonction calculable, la calculabilité relative peut recevoir des définitions équivalentes dans de nombreux modèles de calcul différents. Ceci est généralement accompli en complétant le modèle de calcul avec une opération primitive supplémentaire qui demande si un entier donné est membre de A . On peut aussi dire que f est calculable dans g en identifiant g à son graphe.

Théorie de la récursion supérieure

La théorie hyperarithmétique étudie les ensembles qui peuvent être calculés à partir d'un nombre ordinal calculable d'itérations du saut de Turing de l'ensemble vide. Cela équivaut à des ensembles définis à la fois par une formule universelle et existentielle dans le langage de l'arithmétique du second ordre et à certains modèles d' hypercalcul . Des théories de récursivité encore plus générales ont été étudiées, telles que la théorie de la récursivité E dans laquelle n'importe quel ensemble peut être utilisé comme argument d'une fonction E-récursive.

Hyper-calcul

Bien que la thèse de Church-Turing affirme que les fonctions calculables incluent toutes les fonctions avec des algorithmes, il est possible d'envisager des classes plus larges de fonctions qui assouplissent les exigences que les algorithmes doivent posséder. Le domaine de l' hypercalcul étudie des modèles de calcul qui vont au-delà du calcul normal de Turing.

Voir également

• Nombre calculable
• Méthode efficace
• Théorie du calcul
• Théorie de la récursivité
• Diplôme de Turing
• Hiérarchie arithmétique
• Hypercalcul
• Algorithme super-récursif
• Fonction semi-calculable

Les références

• Cutland, Nigel. Calculabilité . Cambridge University Press, 1980.
• Enderton, HB Éléments de la théorie de la récursivité. Manuel de logique mathématique (Hollande du Nord 1977) pp. 527-566.
• Rogers, H. Théorie des fonctions récursives et calcul efficace (McGraw-Hill 1967).
• Turing, A. (1937), Sur les nombres calculables, avec une application au problème Entscheidungs . Actes de la London Mathematical Society , série 2, volume 42 (1937), p.230-265. Réimprimé dans M. Davis (éd.), The Undecidable , Raven Press, Hewlett, NY, 1965.