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: 2   Last Post: Nov 6, 2013 8:57 AM

 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 6, 2013 8:57 AM

On Wednesday, November 6, 2013 5:25:52 AM UTC-8, Ben Bacarisse wrote:
> grahamcooper7@gmail.com writes:
>
>
>

> > On Tuesday, November 5, 2013 7:38:48 PM UTC-8, Ben Bacarisse wrote:
>
> <snip>
>

> >> That's an argument that one representation (I'm guessing -- you don't
>
> >> actually give the input representation) and method fails. Whilst I am
>
> >> sure they all do, any argument for that must be more general.
>
> >>
>
> >> To all intents a purposes, it probably suffices to say that neither
>
> >>
>
> >> { "x*y=z" | v(x) * v(y) = v(z) }
>
> >> { interleave(x, y, z) | v(x) * v(y) = v(z) }
>
> >>
>
> >> is regular.
>
> >
>
> > Possibly, that seems a lot more obscure than the fact
>
> > that multiplication requires > O(n) internal states and
>
> > hence a non-finite memory Turing Machine to calculate.
>
>
>
> But is it true? Can you prove it? I can prove it for the above
>
> representations, but, as the addition example shows, the representation
>
> matters.

No it doesn't. You only need any 1 representation to show it works on a FSM.

Proof complete!

>
>
>

> > I don't recall if Least Significant Bit first was used
>
> > but it seems a reasonable assumption.
>
> >
>
> > Try to program something like this for multiplication?
>
>
>
> Least significant bit first is not enough, even for addition. If the
>
> input is "x0x1x2....xn+y0y1y2...ym" you can't do the addition using an
>
> FSM. (I've re-framed the example, because you are using the notion of a
>
> transducer, rather than a decision problem).
>

And many other representation methods of numbers of unbounded length
are not suitable for finite state devices, obviously.

However, FSM's can do addition - FACT!

---------

Is it possible some obscure representation of numbers everybody missed
works for unbounded multiplication on FSM's... yes!

You could represent number n by a sequence of products of n up to n^2.

7
<=>

"1x7=7
2x7=14
3x7=21
4x7=28
5x7=35
6x7=42
7x7=49"

This ENTIRE STRING is the number 7.

Now you can run any 2 numbers in that format
into a FSM and it will output the product!

Herc

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