Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème de Post
Résumé
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
Arithmetical hierarchy#Relation to Turing machines
The statement of Post's theorem uses several concepts relating to definability and recursion theory. This section gives a brief overview of these concepts, which are covered in depth in their respective articles.
The arithmetical hierarchy classifies certain sets of natural numbers that are definable in the language of Peano arithmetic. A formula is said to be if it is an existential statement in prenex normal form (all quantifiers at the front) with alternations between existential and universal quantifiers applied to a formula with bounded quantifiers only. Formally a formula in the language of Peano arithmetic is a formula if it is of the form
where contains only bounded quantifiers and Q is if m is even and if m is odd.
A set of natural numbers is said to be if it is definable by a formula, that is, if there is a formula such that each number is in if and only if holds. It is known that if a set is then it is for any , but for each m there is a set that is not . Thus the number of quantifier alternations required to define a set gives a measure of the complexity of the set.
Post's theorem uses the relativized arithmetical hierarchy as well as the unrelativized hierarchy just defined. A set of natural numbers is said to be relative to a set , written , if is definable by a formula in an extended language that includes a predicate for membership in .
While the arithmetical hierarchy measures definability of sets of natural numbers, Turing degrees measure the level of uncomputability of sets of natural numbers. A set is said to be Turing reducible to a set , written , if there is an oracle Turing machine that, given an oracle for , computes the characteristic function of .
The Turing jump of a set is a form of the Halting problem relative to . Given a set , the Turing jump is the set of indices of oracle Turing machines that halt on input when run with oracle .
Source officielle
À propos de ce résultat
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.