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 5, 2013 10:08 PM


On Tuesday, November 5, 2013 2:24:21 PM UTC8, Ben Bacarisse wrote: > grahamcooper7@gmail.com writes: > > > > > On Tuesday, November 5, 2013 7:19:20 AM UTC8, Ben Bacarisse wrote: > > >> grahamcooper7@gmail.com writes: > > >> <snip> > > >> > This is similar to a FINITE STATE MACHINE can do ADDITION > > >> > but a TURING MACHINE is needed to MULTIPY! > > >> > > >> An interesting point. > > >> > > >> A finite state machine can only do addition if the problem is defined in > > >> a particular way. For example, no FSM can recognise the language > > >> > > >> La = { "x+y=z"  v(x) + v(y) = v(z) } > > >> > > >> Here x, y and z are 0/1 strings (least significant bit first), and the > > >> v() function maps strings to the obvious values. However, if we define > > >> interleave(x, y, z) as the string > > >> > > >> x0 y0 z0 x1 y1 z1 ... > > >> > > >> (with missing digits replaced by 0) then the language > > >> > > >> Li = { interleave(x, y, z)  v(x) + v(y) = v(z) } > > >> > > >> *is* regular. If I were still teaching, I'd set finding a regular > > >> expression that recognises (some form of) addition as an exercise. > > >> > > >> Does that count as an FSM "doing addition"? Your call. > > >> > > >> That no similar fancy representation permits a FSM to do multiplication > > >> probably depends on what's permitted, but nothings reasonable springs > > >> to mind. > > > > > > Yes fancy representations allowed! > > > > > > 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.
> > > > Addition you can output the result so far so there > > > is no bound on input size even with a finite device. > > > > That's too general, in my opinion. You need a funny representation that > > makes the question rather debatable  one could argue that the > > representation has done most of the work of the addition. > >
ADDITION FINITE STATE MACHINE
START 1> ONESOFAR 1/0> CARRY \ 0> ZEROSOFAR <1/1 <0/0
only a few links are shown.
If that model doesn't do addition, then you must also think Turing Machines don't do calculus!

I was using Peano Multiplication as a 2 argument function..
[ + X Z ]
SHOULD BE: [ + X Y ANSWER ]
hence my last Peano Arithmetic Multiplier didn't work!
x [s[s 0]] [s[s[s 0]]] A ? A = s s s s s s 0
2 x 3 = 6
Herc  www.PrologDatabase.com



