Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: AN ERROR IN PEANO ARITHMETIC! x X [ s Y ] [ + X Z ] <- x X Y Z
Replies: 3   Last Post: Nov 5, 2013 3:48 PM

 Messages: [ Previous | Next ]
 Graham Cooper Posts: 4,495 Registered: 5/20/10
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 UTC-8, 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.
>
>
>
>
>
>
> 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

Date Subject Author
11/5/13 Graham Cooper
11/5/13 Ben Bacarisse
11/5/13 Ben Bacarisse
11/5/13 Graham Cooper