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

Topic: AN ERROR IN PEANO ARITHMETIC! x X [ s Y ] [ + X Z ] <- x X Y Z
Replies: 3   Last Post: Nov 5, 2013 10:21 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,319
Registered: 5/20/10
Re: AN ERROR IN PEANO ARITHMETIC! x X [ s Y ] [ + X Z ] <- x X
Y Z

Posted: Nov 5, 2013 10:08 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Tuesday, November 5, 2013 2:24:21 PM UTC-8, Ben Bacarisse wrote:
> grahamcooper7@gmail.com writes:
>
>
>

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



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.