Undecidability of the first-order arithmetic \(A[P(x),2x,x+1]\)

DOI10.1016/0022-0000(79)90033-3zbMath0414.03006OpenAlexW2028367584MaRDI QIDQ599047

Sumit K. Garg

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(79)90033-3

zbMATH Keywords

undecidabilitysatisfiability problemreachability problemfirst order arithmeticfirst order theorymonadic second order theorytwo dimensional finite automata

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25)

Cites Work

• On causal \(\omega^2\)-systems
• Decidability and essential undecidability
• Weak Second‐Order Arithmetic and Finite Automata
• Restricted Set-Theoretical Definitions in Arithmetic
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor

This page was built for publication: Undecidability of the first-order arithmetic \(A[P(x),2x,x+1]\)