Natural limitations of decision procedures for arithmetic with bounded quantifiers

DOI10.1007/BF02023011MaRDI QIDQ3674633zbMATH OpenFDO

Authors Daniele Mundici

Publication date 1983

Published in Archiv für Mathematische Logik und Grundlagenforschung (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/138005

zbMATH Keywords

bounded arithmeticTuring machinecomplexity of decision proceduresconcrete lower bounds for the complexity of theoriespractical decidabilityunfeasible computation

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Cites work

• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3550662 (Why is no real title available?)
• scientific article; zbMATH DE number 3559512 (Why is no real title available?)
• scientific article; zbMATH DE number 3799636 (Why is no real title available?)
• A lower bound for the complexity of Craig's interpolants in sentential logic
• Compactness=JEP in any logic
• Duality Between Logics and Equivalence Relations
• Logical Reversibility of Computation
• Practical decidability
• Quantum mechanical Hamiltonian models of discrete processes that erase their own histories: Application to Turing machines
• Robinson's Consistency Theorem in Soft Model Theory
• The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines

This page was built for publication: Natural limitations of decision procedures for arithmetic with bounded quantifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3674633)