fonction calculable
Locution nominaleFéminin\fɔ̃k.sjɔ̃ kal.ky.labl\
Étymologie
Locution composée de fonction et de calculable. fonction est emprunté au latin functio (« accomplissement, exécution »), dérivé du verbe fungor (« s’acquitter de, accomplir ») ; le mot a été repris en latin scientifique par le mathématicien allemand Gottfried Wilhelm Leibniz à la fin du XVIIᵉ siècle pour désigner une grandeur dépendant d’une autre, puis francisé dans ce sens mathématique ; calculable est dérivé de calculer (du bas latin latin calculare (« compter, calculer »), lui-même dérivé de calculus (« caillou servant à compter »), à l’aide du suffixe -able. La locution elle-même, comme notion mathématique précise, apparaît dans les années , lors de la formalisation de la théorie de la calculabilité par Alonzo Church, Alan Turing, Kurt Gödel et Stephen Kleene, en réponse au problème de la décision (Entscheidungsproblem) posé par David Hilbert.
Logique, Mathématiques Fonction dont la valeur, pour chaque argument de son domaine de définition, peut être obtenue au moyen d’un algorithme, c’est-à-dire d’une procédure mécanique effective et finie, par exemple une machine de Turing qui s’arrête sur toute entrée.
- Une réduction de A vers B est une fonction calculable f:D→D' qquad x∈X⟺f(x)∈YAnca Muscholl, « Complexité et calculabilité », Université de Bordeaux, 3 octobre 2022.
- Il est clairement impossible d’unifier toutes les approches : par exemple toute fonction calculable en analyse récursive est nécessairement continue, alors que des fonctions discontinues sont calculables dans le modèle initial de Blum Shub et Smale (1989).Olivier Bournez, Gilles Dowek, Rémi Gilleron, Serge Grigorieff, Jean-Yves Marion, Simon Perdrix, Sophie Tison, « Informatique théorique : Calculabilité, Décidabilité et logique », Institut de recherche en informatique fondamentale (IRIF).
1 autre exemple
- Une fonction f est calculable s’il existe une méthode précise (un algorithme) qui, étant donné un argument x, permet d’obtenir l’image f(x) en un nombre fini d’étapes. Une fonction calculable est une fonction calculable par une machine de Turing.
- Synonymes
- fonction générale récursive, fonction μ-récursive totale, fonction récursive, fonction récursive totale
- Antonymes
- fonction indécidable, fonction non calculable
- Dérivés
- calculabilité, fonction semi-calculable
- Apparentés
- algorithme, décidable, fonction partielle récursive, fonction récursive primitive, machine de Turing, problème de l’arrêt, thèse de Church
- Hyperonymes
- fonction
- Hyponymes
- fonction récursive primitive