|
2 | deleted 237 characters in body | ||
|
The possibility to define natural number multiplication in the language $L(+,2^{(\cdot)})$ makes that theory undecidable. What about is the complexity of the theory of addition (Presburger arithmetic) augmented by a unary predicate that recognizes powers of 2? Side question: does anyone know terse unsolved problems shorter to state in the language $L(+,2^{(\cdot)})$ than in $L(+,\times)$? |
||||
|
|
1 |
|
||
Theory of addition and a predicate that recognizes powers of 2The possibility to define natural number multiplication in the language $L(+,2^{(\cdot)})$ makes that theory undecidable. What about the theory of addition (Presburger arithmetic) augmented by a unary predicate that recognizes powers of 2? Side question: does anyone know terse unsolved problems shorter to state in the language $L(+,2^{(\cdot)})$ than in $L(+,\times)$?
|
||||
