20 Jul
2012
20 Jul
'12
6:10 p.m.
Pressburger arithmetic deals with the theory of addition, more or less, and is decidable. My recent fiddling with gcd reminded me that adding "inversion" (1/x) to addition is strictly less powerful than adding multiplication. Notice that simply adding inversion doesn't give you division (y/x), because that would require multiplication (y*(1/x)). Has anyone studied Pressburger plus inversion? Just off-hand, I would guess that it is still decidable, and perhaps not increase the complexity all that much.