Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Graham Cooper

Posts: 4,280
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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.
>
>
>
> 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



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.