MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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 2

The 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)$?