Natural limitations of decision procedures for arithmetic with bounded quantifiers

DOI10.1007/BF02023011zbMATH Open0523.03028MaRDI QIDQ3674633FDOQ3674633

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)