The Math Forum

Search All of the Math Forum:

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

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

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Ben Bacarisse

Posts: 1,972
Registered: 7/4/07
Re: AN ERROR IN PEANO ARITHMETIC! x X [ s Y ] [ + X Z ] <- x X Y Z
Posted: Nov 5, 2013 10:38 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply writes:
>> > 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.


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

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.