Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Re: AN ERROR IN PEANO ARITHMETIC! x X [ s Y ] [ + X Z ] < x X Y Z
Posted:
Nov 6, 2013 8:57 AM


On Wednesday, November 6, 2013 5:25:52 AM UTC8, Ben Bacarisse wrote: > grahamcooper7@gmail.com writes: > > > > > On Tuesday, November 5, 2013 7:38:48 PM UTC8, Ben Bacarisse wrote: > > <snip> > > >> That's an argument that one representation (I'm guessing  you don't > > >> actually give the input representation) and method fails. Whilst I am > > >> sure they all do, any argument for that must be more general. > > >> > > >> To all intents a purposes, it probably suffices to say that neither > > >> > > >> { "x*y=z"  v(x) * v(y) = v(z) } > > >> { interleave(x, y, z)  v(x) * v(y) = v(z) } > > >> > > >> is regular. > > > > > > Possibly, that seems a lot more obscure than the fact > > > that multiplication requires > O(n) internal states and > > > hence a nonfinite memory Turing Machine to calculate. > > > > But is it true? Can you prove it? I can prove it for the above > > representations, but, as the addition example shows, the representation > > matters.
No it doesn't. You only need any 1 representation to show it works on a FSM.
Proof complete!
> > > > > I don't recall if Least Significant Bit first was used > > > but it seems a reasonable assumption. > > > > > > Try to program something like this for multiplication? > > > > Least significant bit first is not enough, even for addition. If the > > input is "x0x1x2....xn+y0y1y2...ym" you can't do the addition using an > > FSM. (I've reframed the example, because you are using the notion of a > > transducer, rather than a decision problem). >
And many other representation methods of numbers of unbounded length are not suitable for finite state devices, obviously.
However, FSM's can do addition  FACT!

Is it possible some obscure representation of numbers everybody missed works for unbounded multiplication on FSM's... yes!
You could represent number n by a sequence of products of n up to n^2.
7 <=>
"1x7=7 2x7=14 3x7=21 4x7=28 5x7=35 6x7=42 7x7=49"
This ENTIRE STRING is the number 7.
Now you can run any 2 numbers in that format into a FSM and it will output the product!
Herc



