In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an important tool in effective descriptive set theory.
The central focus of hyperarithmetic theory is the sets of natural numbers known as hyperarithmetic sets. There are three equivalent ways of defining this class of sets; the study of the relationships between these different definitions is one motivation for the study of hyperarithmetical theory.
The first definition of the hyperarithmetic sets uses the analytical hierarchy.
A set of natural numbers is classified at level of this hierarchy if it is definable by a formula of second-order arithmetic with only existential set quantifiers and no other set quantifiers. A set is classified at level of the analytical hierarchy if it is definable by a formula of second-order arithmetic with only universal set quantifiers and no other set quantifiers. A set is if it is both and . The hyperarithmetical sets are exactly the sets.
The definition of hyperarithmetical sets as does not directly depend on computability results. A second, equivalent, definition shows that the hyperarithmetical sets can be defined using infinitely iterated Turing jumps. This second definition also shows that the hyperarithmetical sets can be classified into a hierarchy extending the arithmetical hierarchy; the hyperarithmetical sets are exactly the sets that are assigned a rank in this hierarchy.
Each level of the hyperarithmetical hierarchy is indexed by a countable ordinal number (ordinal), but not all countable ordinals correspond to a level of the hierarchy. The ordinals used by the hierarchy are those with an ordinal notation, which is a concrete, effective description of the ordinal.
An ordinal notation is an effective description of a countable ordinal by a natural number. A system of ordinal notations is required in order to define the hyperarithmetic hierarchy.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Explore les propriétés théoriques et la puissance pratique des réseaux neuronaux récurrents, y compris leur relation avec les machines d'état et l'exhaustivité de Turing.
En théorie de la calculabilité, le saut de Turing, du nom d'Alan Turing, est une opération qui attribue à chaque problème de décision un problème de décision plus difficile avec la propriété que n'est pas décidable par une machine à oracle relative à . Le saut est appelé opérateur de saut car il augmente le degré de Turing du problème . Autrement dit, le problème n'est pas à . Le théorème de Post établit une relation entre l'opérateur de saut de Turing et la hiérarchie arithmétique des ensembles de nombres naturels.
Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980). Thus effective descriptive set theory combines descriptive set theory with recursion theory. Effective Polish space An effective Polish space is a complete separable metric space that has a computable presentation. Such spaces are studied in both effective descriptive set theory and in constructive analysis.
En mathématiques, en particulier en calculabilité et en théorie des ensembles, un ordinal est dit calculable ou récursif s'il existe un bon ordre calculable d'un sous-ensemble calculable des nombres naturels ayant le type d'ordre . Il est facile de vérifier que est calculable. On montre également que le successeur d'un ordinal calculable est calculable, et que l'ensemble de tous les ordinaux calculables est fermé vers le bas. La borne supérieure de tous les ordinaux calculables est appelé l'ordinal de Church-Kleene, le premier ordinal non récursif, et noté .