A Decision Method for Elementary Algebra and Geometry¶
Tarski, A. (1951). A Decision Method for Elementary Algebra and Geometry. University of California Press.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Decidability Computability
- The failure taxonomy completes the picture from the logic side: the provable formulas of first-order logic are semi-decidable — proof search halts with "yes" on every theorem but may loop forever on a non-theorem — and the theory of real-closed fields is decidable yet its decision procedure is doubly-exponential, so "decidable" never means "cheap."
This sourceProves the theory of real-closed fields (elementary geometry over the reals) decidable by quantifier elimination, with a high-complexity decision procedure.
- The failure taxonomy completes the picture from the logic side: the provable formulas of first-order logic are semi-decidable — proof search halts with "yes" on every theorem but may loop forever on a non-theorem — and the theory of real-closed fields is decidable yet its decision procedure is doubly-exponential, so "decidable" never means "cheap."
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:7b906a52f13b · see in the full table