Decider (Turing machine)In computability theory, a decider is a Turing machine that halts for every input. A decider is also called a total Turing machine as it represents a total function. Because it always halts, such a machine is able to decide whether a given string is a member of a formal language. The class of languages which can be decided by such machines is the set of recursive languages. Given an arbitrary Turing machine, determining whether it is a decider is an undecidable problem.
Gentzen's consistency proofGentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936. It shows that the Peano axioms of first-order arithmetic do not contain a contradiction (i.e. are "consistent"), as long as a certain other system used in the proof does not contain any contradictions either. This other system, today called "primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal ε0", is neither weaker nor stronger than the system of Peano axioms.
BlooP and FlooPand () (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.
HyperopérationEn mathématiques, les hyperopérations (ou hyperopérateurs) constituent une suite infinie d'opérations qui prolonge logiquement la suite des opérations arithmétiques élémentaires suivantes : addition (n = 1) : multiplication (n = 2) : exponentiation (n = 3) : Reuben Goodstein proposa de baptiser les opérations au-delà de l'exponentiation en utilisant des préfixes grecs : tétration (n = 4), pentation (n = 5), hexation (n = 6), etc. L'hyperopération à l'ordre n peut se noter à l'aide d'une flèche de Knuth au rang n – 2.
Wilhelm AckermannWilhelm Ackermann (1896-1962) est un mathématicien allemand, célèbre pour la fonction d'Ackermann (1925) qui est un exemple important de la théorie de la calculabilité. Sa thèse (1924) donne une preuve détaillée de la cohérence de l'. Il fut professeur dans le secondaire, à Burgsteinfurt de 1929 à 1948, puis à Lüdenscheid jusqu'à sa retraite en 1961. Il fut membre correspondant de l'Académie des sciences de Göttingen et professeur honoraire de l'université de Münster.
Hiérarchie de croissance rapideEn théorie de la calculabilité et en théorie de la démonstration, une hiérarchie de croissance rapide (parfois appelée une hiérarchie de Grzegorczyk étendue) est une famille, indexée par les ordinaux, de fonctions rapidement croissantes fα : N → N (où N est l'ensemble des entiers naturels {0, 1, ...}, et α est un ordinal inférieur à un certain ordinal dénombrable généralement très grand). Un exemple fondamental est la hiérarchie de Wainer, s'étendant à tous les α < ε0.
Random access machineEn informatique théorique, la machine RAM, pour Random Access Machine, est un modèle abstrait d'ordinateur destiné à étudier des algorithmes. une machine qui ne fait qu'effectuer des calculs sur des nombres, codés sous la forme d'une suite de symboles. Ces calculs vont donc transformer une suite de symboles en une autre. Les suites de symboles manipulées sont appelées des données, tandis que les calculs qui transforment une chaîne de « caractères » en une autre sont appelées des instructions.
Loop variantIn computer science, a loop variant is a mathematical function defined on the state space of a computer program whose value is monotonically decreased with respect to a (strict) well-founded relation by the iteration of a while loop under some invariant conditions, thereby ensuring its termination. A loop variant whose range is restricted to the non-negative integers is also known as a bound function, because in this case it provides a trivial upper bound on the number of iterations of a loop before it terminates.
