Hiérarchie arithmétique

thumb|Illustration de la hiérarchie arithmétique. En logique mathématique, plus particulièrement en théorie de la calculabilité, la hiérarchie arithmétique, définie par Stephen Cole Kleene, est une hiérarchie des sous-ensembles de l'ensemble N des entiers naturels définissables dans le langage du premier ordre de l'arithmétique de Peano. Un ensemble d'entiers est classé suivant les alternances de quantificateurs d'une formule sous forme prénexe qui permet de le définir. Les premiers niveaux de la hiérarchie correspondent à la classe des ensembles récursivement énumérables (Σ10) et à celle des ensembles dont le complémentaire est récursivement énumérable (Π10), leur intersection étant la classe des ensembles récursifs (Δ10). Pour définir la hiérarchie des sous-ensembles définissables de N, on peut utiliser une hiérarchie des formules (au sens du calcul des prédicats) de l'arithmétique. Il s'agit ici de formules du premier ordre, ce qu'indique l'exposant 0, quand on parle de formule Σn0 ou Πn0. De même, la hiérarchie analytique utilise des formules du second ordre, ce qui est dénoté par l'exposant 1. Dans la suite, on omettra l'exposant 0 car il n'y a pas de risque de confusion. Au niveau 0, les classes des formules Σ0 et Π0 sont identiques. Ce sont les formules à quantificateurs bornés du langage de l'arithmétique de Peano, c'est-à-dire celles qui sont construites à partir des égalités polynomiales (addition et multiplication sont les seuls symboles de fonctions utilisés), avec les connecteurs usuels, et les quantificateurs universels et existentiels bornés ∃x≤t ... et ∀x≤t .... Par exemple, cette formule à deux variables libres x et z est Σ0 (ou Π0) : (∃y≤z) 2z=(x+y)(x+y+1)+2y est Σ0 (ou Π0). On définit ensuite inductivement les classes des formules Σn et Πn, pour un entier naturel n non nul. Si A est une formule Σ0 (ou Π0), ∃x A est une formule Σ1 et ∀x A une formule Π1 ; Si S est une formule Σn, si P est une formule Πn, et si x est une variable quelconque (qui peut ou non apparaître libre dans S et P) alors : ∃x S reste Σn ; ∃x P est une formule Σn+1 ; ∀x S est une formule Πn+1 ; ∀x P reste Πn.

À 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.

Publications associées (12)

Unités associées (3)

Concepts associés (25)

Cours associés (2)

Séances de cours associées (6)

Problème de l'arrêt

vignette|L'animation illustre une machine impossible : il n'y a pas de machine qui lit n'importe quel code source d'un programme et dit si son exécution termine ou non. En théorie de la calculabilité, le problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette entrée ou non.

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.

Turing reduction

In computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine which decides problem given an oracle for (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems. If a Turing reduction from to exists, then every algorithm for can be used to produce an algorithm for , by inserting the algorithm for at each place where the oracle machine computing queries the oracle for .

QFT without infinities and hierarchy problem

Sander Johannes Nicolaas Mooij

The standard way to do computations in Quantum Field Theory (QFT) often results in the requirement of dramatic cancellations between contributions induced by a "heavy" sector into the physical observables of the "light" (or low energy) sector - the phenome ...

ELSEVIER2023

Placement of Virtual Containers on NUMA systems: A Practical and Comprehensive Model

Baptiste Joseph Eustache Lepers

Our work addresses the problem of placement of threads, or virtual cores, onto physical cores in a multicore NUMA system. Different placements result in varying degrees of contention for shared resources, so choosing the right placement can have a large ef ...

2018

USENIX ASSOC2018

MATH-483: Gödel and recursivity

Gödel incompleteness theorems and mathematical foundations of computer science

MATH-318: Set theory

Set Theory as a foundational system for mathematics. ZF, ZFC and ZF with atoms. Relative consistency of the Axiom of Choice, the Continuum Hypothesis, the reals as a countable union of countable sets,

Théorie de la complexité : P et NP CS-119(c): Information, Computation, Communication

Explore les classes de complexité P et NP, les algorithmes pratiques, les problèmes non polynomiaux et la vérification efficace des solutions.

Systèmes intelligents distribués: Efficacité énergétique dans les réseaux de capteurs sans fil ENG-466: Distributed intelligent systems

Découvrez les principes d'économie d'énergie dans les réseaux de capteurs sans fil, en explorant des applications motivantes et des algorithmes intelligents pour l'efficacité énergétique.

Contrôle prédictif du modèle non linéaire: étapes de stabilité et de conception EE-715: Optimal control

Explore les principes de contrôle prédictif du modèle non linéaire, l'analyse de stabilité, les étapes de conception et les considérations pratiques.