email@example.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