[math-fun] Logicians: Theory of continued fractions?
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.
This reminds me of Problem 1 in Donald J Newman's "Problem Seminar": Derive the operations of addition, subtraction, multiplication, and division from subtraction and reciprocal. On Fri, Jul 20, 2012 at 5:09 PM, Henry Baker <hbaker1@pipeline.com> wrote:
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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
That's pretty cool. I've gotten part of the way, but I'm stuck on deriving 1. The only way I've found of deriving the constant 1 (given a value x that is known to not be zero) is to repeatedly iterate f(x)=(x+1/x)/2. This converges quadratically, but it's not a classical ruler-and-compass solution. Is "1" itself the biggest problem in "problem 1"? - Robert (If I can assume that 1 is given then RIES gives me the rest, I'll explain if anyone is interested.) On 7/20/12, Thane Plambeck <tplambeck@gmail.com> wrote:
This reminds me of Problem 1 in Donald J Newman's "Problem Seminar":
Derive the operations of addition, subtraction, multiplication, and division from subtraction and reciprocal.
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
participants (4)
-
Gareth McCaughan -
Henry Baker -
Robert Munafo -
Thane Plambeck