Oracle (machine de Turing)vignette|upright=2|Une machine de Turing avec oracle peut faire appel à une boîte noire (oracle). En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire. En particulier, l'oracle peut résoudre en temps constant un problème indécidable comme le problème de l'arrêt.
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.
Oméga de Chaitinthumb|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.
Problème du mot pour les groupesEn mathématiques, plus précisément dans le domaine de la théorie combinatoire des groupes, le problème du mot pour un groupe de type fini G est le problème algorithmique de décider si deux mots en les générateurs du groupe représentent le même élément. Plus précisément, si X un ensemble fini de générateurs pour G, on considère le langage formel constitué des mots sur X et son ensemble d'inverses formels qui sont envoyés par l'application naturelle sur l'identité du groupe G.
Machine abstraiteEn informatique théorique, et notamment en théorie des automates, un automate abstrait ou une machine abstraite est un modèle théorique d'un ordinateur digital et discret. Il importe peu, dans ce cadre, de savoir si cet appareil peut effectivement être construit, mais plutôt d'appréhender, par ce modèle simplifié, le fonctionnement des machines, et de les comparer entre eux. La notion d'automate ou de machine abstraite, aussi appelé « modèle de machine » joue un rôle central en informatique théorique.
Complexité de KolmogorovEn informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, , chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff.
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.
ComputabilityComputability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power.
