News for hackers. Stuff that matters.
Re:Manuel Blum: Advice to a beginning graduate student by wittgenstein on Saturday December 25, 2010 @03:35AM (#2038710)
"For example, Finite Automata can add but not multiply."

Can someone please explain why this is true? If it can add, how can it not multiply if multiplication is repeated addition?

Re:Manuel Blum: Advice to a beginning graduate student by cscheid on Saturday December 25, 2010 @05:44AM (#2038782)
Roughly because the number of times it needs to sum to get a multiply is not constant; it depends on the input. Think about writing the automaton -- how would you know when to stop? You're only given one automaton to write, and you don't know ahead of time how big either of the input numbers are.
Re:Manuel Blum: Advice to a beginning graduate student by djcapelis on Saturday December 25, 2010 @05:48AM (#2038786)
You can make the FSM repeat the addition, but you can't give it the memory it needs to know when to stop.

If you need more explanation just try implementing it, you should see where the problem is fairly quickly. :)

Re:Manuel Blum: Advice to a beginning graduate student by sesqu on Sunday December 26, 2010 @09:55AM (#2040608)
So how do you get it to add? Specifically, what representation of arbitrary numbers are we using with our finite automaton? Infinite read-only tape plus infinite write-only tape for output, in base 10? If so, it should be simple to do multiplication by representing the numbers in factorized form and applying our adder.