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



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


On Tuesday, November 5, 2013 7:38:48 PM UTC8, Ben Bacarisse wrote: > grahamcooper7@gmail.com writes: > > <snip> > > >> > But all of them require unlimited memory to perform unlimited size > > >> > number multiplication. > > >> > > >> It would be nice to see a proof. I don't have one. > > > > > > There is a proof but I don't recall it. > > > > > > The number of states of the machine is less than the > > > intermediate sums to perform multiplication. > > > > > > Starting with Least Significant Bit > > > > > > 010101010101 > > > X > > > 010101 > > > ____________ > > > > > > > > > Now you have X carry states, LEN(TERM2) > > > and only Y internal states. > > > > 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.
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?
ADDITION FINITE STATE MACHINE
START 1> ONESOFAR 1/0> CARRY \ 0> ZEROSOFAR <1/1 <0/0
You can't!
Herc



