Natural limitations of decision procedures for arithmetic with bounded quantifiers

DOI10.1007/BF02023011zbMath0523.03028MaRDI QIDQ3674633

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 computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum mechanical Hamiltonian models of discrete processes that erase their own histories: Application to Turing machines
• Practical decidability
• The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines
• Robinson's Consistency Theorem in Soft Model Theory
• Compactness=JEP in any logic
• Duality Between Logics and Equivalence Relations
• A lower bound for the complexity of Craig's interpolants in sentential logic
• Logical Reversibility of Computation