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 2:33 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 2:33 AM

On Tuesday, November 5, 2013 7:38:48 PM UTC-8, Ben Bacarisse wrote:
> grahamcooper7@gmail.com writes:
>
> <snip>
>

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

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?

START --1--> ONESOFAR --1/0--> CARRY
\
---0---> ZEROSOFAR
<--1/1---
<---0/0---

You can't!

Herc

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