Concept
Problème de l'arrêt
Concepts associés (52)
Turing-complet
En informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing-complete) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing. Dans un tel système, il est donc possible de programmer n'importe quelle machine de Turing. Cette notion est rendue pertinente par la thèse de Church, qui postule l’existence d’une notion naturelle de calculabilité.
Système de tague
En informatique théorique, plus précisément en calculabilité, un système de tague (tag system en anglais) est un modèle de calculabilité défini par Emil Leon Post en 1943 comme système de réécriture. C'est un cas particulier de système de Post. Ce modèle est Turing-complet : toute fonction calculable peut être représentée par un système de tague de Post. Un système de tague est défini par : un entier naturel m (nombre de lettres du préfixe, à effacer après chaque itération) ; un alphabet fini A ; un mot initial écrit avec l'alphabet A; une règle de réécriture par lettre de l'alphabet : à toute lettre a, on associe un mot P(a).
Informaticien
Un informaticien ou une informaticienne est une personne qui exerce un métier dans l'étude, la conception, la production, la gestion ou la maintenance des systèmes de traitement de l'information. La définition générale désigne le technicien ou l'ingénieur spécialiste d'un système informatique. Femmes en informatique Le métier d'informaticien apparaît à la fin du avec l’émergence de la mécanographie. Celle-ci consiste alors à traiter l'information à l'aide de systèmes électromécaniques.
Récursivement énumérable
En théorie de la calculabilité, un ensemble d'entiers naturels est récursivement énumérable ou semi-décidable si : il existe un algorithme qui prend un entier naturel en entrée, et qui s'arrête exactement sur les entiers de ; ou, de manière équivalente : il existe un procédé algorithmique qui, au cours de son fonctionnement, énumère en sortie tous les entiers de et seulement ceux-ci (il est possible, et même nécessaire quand est infini, qu'il ne s'arrête pas).
Ensemble récursif
En 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.
BlooP and FlooP
and () (Bounded loop and Free loop) are simple programming languages designed by Douglas Hofstadter to illustrate a point in his book Gödel, Escher, Bach. BlooP is a non-Turing-complete programming language whose main control flow structure is a bounded loop (i.e. recursion is not permitted). All programs in the language must terminate, and this language can only express primitive recursive functions. FlooP is identical to BlooP except that it supports unbounded loops; it is a Turing-complete language and can express all computable functions.
Machine à registres illimités
En informatique, une machine à registres illimités ou URM (de l'anglais : Unlimited Register Machine) est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tout comme les machines de Turing et le lambda-calcul. Une URM est Turing-complète. Les registres de la machine sont représentés par : et peuvent contenir des éléments de . Un programme pour cette machine est représenté par toute suite de la forme : qui contient une suite finie d'instructions.
Oméga de Chaitin
thumb|right|upright=1.2|Un nombre Oméga de Chaitin est une suite de bits représentant, sous forme concentrée, la solution du problème de l'arrêt pour tous les programmes d'une machine de Turing universelle donnée. En théorie algorithmique de l'information, une constante 'Oméga de Chaitin' (nombres définis et étudiés par Gregory Chaitin) caractérise de manière univoque et mathématiquement précise un nombre réel, qui possède la particularité d'être aléatoire et de ne pas être calculable au sens de Turing : un algorithme donné ne permet de calculer qu'un nombre fini de ses décimales.
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.
Machine de Turing universelle
vignette|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.