Decidability of first-order theories of the real numbers
Résumé
In mathematical logic, a first-order language of the real numbers is the set of all well-formed sentences of first-order logic that involve universal and existential quantifiers and logical combinations of equalities and inequalities of expressions over real variables. The corresponding first-order theory is the set of sentences that are actually true of the real numbers. There are several different such theories, with different expressive power, depending on the primitive operations that are allowed to be used in the expression. A fundamental question in the study of these theories is whether they are decidable: that is, is there an algorithm that can take a sentence as input and produce as output an answer "yes" or "no" to the question of whether the sentence is true in the theory.
The theory of real closed fields is the theory in which the primitive operations are multiplication and addition; this implies that, in this theory, the only numbers that can be defined are the real algebraic numbers. As proven by Tarski, this theory is decidable; see Tarski–Seidenberg theorem and Quantifier elimination. Current implementations of decision procedures for the theory of real closed fields are often based on quantifier elimination by cylindrical algebraic decomposition.
Tarski's exponential function problem concerns the extension of this theory to another primitive operation, the exponential function. It is an open problem whether this theory is decidable, but if Schanuel's conjecture holds then the decidability of this theory would follow. In contrast, the extension of the theory of real closed fields with the sine function is undecidable since this allows encoding of the undecidable theory of integers (see Richardson's theorem).
Still, one can handle the undecidable case with functions such as sine by using algorithms that do not necessarily terminate always. In particular, one can design algorithms that are only required to terminate for input formulas that are robust, that is, formulas whose satisfiability does not change if the formula is slightly perturbed.
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.
En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L’indécidabilité est la négation de la décidabilité. Dans les deux cas, il s'agit de formaliser l'idée qu'on ne peut pas toujours conclure lorsque l'on se pose une question, même si celle-ci est sous forme logique. Une proposition (on dit aussi énoncé) est dite décidable dans une théorie axiomatique si on peut la démontrer ou démontrer sa négation dans le cadre de cette théorie.
Explore la décidabilité dans les machines Turing et les langages récursifs.
Explore la machine universelle Turing, sa représentation canonique et son rôle dans la définition des algorithmes et des concepts théoriques d'informatique.
Explore les machines Turing, les langages récursifs, et la décidabilité dans la théorie du calcul.
We study the decision problem for the existential fragment of the theory of power structures. We prove complexity results that parallel the decidability results of Feferman-Vaught for the theories of product structures thereby showing that the construction ...
The popular isolation level multiversion Read Committed (RC) exchanges some of the strong guarantees of serializability for increased transaction throughput. Nevertheless, transaction workloads can sometimes be executed under RC while still guaranteeing se ...
The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...