Fonction récursive primitiveEn théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas de récursion primitive (ou bornée) et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. Elles ont été initialement analysées par la mathématicienne Rózsa Péter. On s'intéresse aux fonctions définies sur l'ensemble des entiers naturels, ou sur les ensembles des -uplets d'entiers naturels, et à valeurs dans .
Ensemble récursifEn théorie de la calculabilité, un ensemble récursif ou ensemble décidable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique est une fonction récursive au sens de la logique mathématique. En d'autres termes, un ensemble est récursif si, et seulement si, il existe une machine de Turing (un programme informatique) permettant de déterminer en un temps fini si un entier quelconque est dans ou pas. Ce type d'ensemble correspond à un concept effectif de John R.
Fonction d'AckermannDans la théorie de la récursivité, la fonction d'Ackermann (aussi appelée fonction d'Ackermann-Péter) est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle est souvent présentée sous la forme qu'en a proposée la mathématicienne Rózsa Péter, comme une fonction à deux paramètres entiers naturels comme arguments et qui retourne un entier naturel comme valeur, noté en général A(m, n).
Castor affairéUn castor affairé est, en théorie de la calculabilité, une machine de Turing qui maximise son « activité opérationnelle » (comme le nombre de pas effectués ou le nombre de symboles écrits avant son arrêt) parmi toutes les machines de Turing d'une certaine classe. Celles-ci doivent satisfaire certaines spécifications et doivent s'arrêter après être lancées sur un ruban vierge. Une fonction du castor affairé, ou fonction du nombre maximal de pas quantifie cette activité maximale pour une machine de Turing à n états ; ce type de fonction n'est pas calculable.
Degré de TuringEn informatique et en logique mathématique, le degré de Turing (nommé d'après Alan Turing) ou le degré d'insolubilité d'un ensemble d'entiers naturels mesure le niveau d'insolubilité algorithmique de l'ensemble. Le concept de degré de Turing est fondamental dans la théorie de la calculabilité, où des ensembles d'entiers naturels sont souvent considérés comme des problèmes de décision. Le degré de Turing d'un ensemble révèle combien il est difficile de résoudre le problème de décision associé à cet ensemble, à savoir, déterminer si un nombre arbitraire est dans l'ensemble donné.
Recursively enumerable languageIn mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages.
Machine de Turing universellevignette|upright=1.5|Une machine de Turing quelconque M réalise un calcul à partir d'une entrée écrite sur son ruban. Une machine de Turing universelle U simule le calcul de M sur l'entrée de M à partir d'une description de M et de l'entrée de M écrits sur le ruban de U. En informatique, plus précisément en informatique théorique, une machine de Turing universelle est une machine de Turing qui peut simuler n'importe quelle machine de Turing sur n'importe quelle entrée.
Fonction successeurEn mathématiques, la fonction successeur est une fonction récursive primitive S telle que S(n) = n+1 pour tout entier naturel n. Par exemple, S(1) = 2 et S(2) = 3. La fonction successeur apparaît dans les axiomes de Peano qui définissent les entiers naturels. Elle n'y est pas définie à partir de l'opération d'addition, mais est une opération primitive qui sert à définir les entiers naturels à partir de 0, mais aussi les autres opérations sur les entiers naturels, dont l'addition.
Machine de TuringEn informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ». Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.
Many-one reductionIn computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem (whether an instance is in ) to another decision problem (whether an instance is in ) using an effective function. The reduced instance is in the language if and only if the initial instance is in its language . Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving .
