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 3:48 PM


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. Addition you can output the result so far so there is no bound on input size even with a finite device.
Herc



