Natural limitations of decision procedures for arithmetic with bounded quantifiers

DOI10.1007/BF02023011zbMATH Open0523.03028MaRDI QIDQ3674633FDOQ3674633

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

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

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)