Andy's Math/CS page

Monday, August 10, 2009

Wit and Wisdom from Kolmogorov

I just learned about a result of Kolmogorov from the '50s that ought to interest TCS fans. Consider circuits operating on real-variable inputs, built from the following gates:

-sum gates, of unbounded fanin;
-arbitrary continuous functions of a single variable.

How expressive are such circuits? Kolmogorov informs us that they can compute any continuous function on n variables. Wow! In fact, one can achieve this with poly(n)-sized, constant-depth formulas alternating between sums and univariate continuous functions (two layers of each type, with the final output being a sum).

Note that sums can also be computed in a tree of fanin-two sums, so this theorem (whose proof I've not yet seen) tells us that fanin-two continuous operations capture continuous functions in the same way that fanin-two Boolean operations capture Boolean computation (actually, even more strongly in light of the poly-size aspect).

This result (strengthening earlier forms found by Kolmogorov and by his student Arnol'd) may, or may not, negatively answer one of Hilbert's problems, the thirteenth--it's not entirely clear even to the experts what Hilbert had intended to ask. But a fun source to learn about this material is a survey/memoir written by A. G. Vitushkin, a former student of Kolmogorov. [a gated document, unfortunately...]

The freewheeling article starts off with Hilbert's problem, but also contains interesting anecdotes about Kolmogorov and the academic scene he presided over in Moscow. Towards the end we get some amusing partisan invective against Claude Shannon, who, scandalously, "entirely stopped his research at an early stage and still kept his position of professor at the Massachusetts Institute of Technology". Vitushkin (who passed away in 2004) apparently bore a grudge over the insufficient recognition of Soviet contributions to information theory. My favorite story relates a not-so-successful visit by Shannon to meet Kolmogorov and features a deft mathematical put-down:

"Kolmogorov was fluent in French and German and read English well, but his spoken English was not very good. Shannon, with some sympathy, expressed his regret that they could not understand each other well. Kolmogorov replied that there were five international languages, he could speak three of them, and, if his interlocutor were also able to speak three languages, then they would have no problems."

Labels:

13 Comments:

  • This is rather surprising to me, though not completely unbelievable, seeing how you allow circuit elements representing *any* continuous single-variable function. An interesting find! I'll check it out.

    By Blogger David Chen, at 1:02 PM  

  • Well, now there is one international language, and Shannon could speak one of them. If Kolmogorov could also speak at least one, they'd have no trouble understanding each other...

    By Anonymous Anonymous, at 11:40 AM  

  • Halmos' Automathography also has interesting anecdotes about Kolmogorov, including a beautiful photograph of him standing in the doorway.

    By Anonymous Anonymous, at 8:36 PM  

  • Care to let your readers know more about Origins of Order?

    By Anonymous Anonymous, at 8:38 PM  

  • Hi anon,

    I read Origins of Order way back in HS, so I'm no longer really competent to describe its contents (probably wasn't then either). However, it was the most exciting, unified, productive demonstration of complex-systems thinking in science that I'd seen, and just a very stimulating book, getting the reader thinking about biological algorithms, the origin of life, coevolution, and other interesting topics.

    I ended up turning to study a different kind of 'complexity theory' than Kauffman and the Santa Fe Institute's, but his ideas provided some of the original sparks and inspiration.

    By Blogger Andy D, at 8:51 PM  

  • Any chances of a new post sometime soon? We miss you!

    By Blogger khane-libe, at 1:43 AM  

  • A New Kind of Grammars: A new kind of generative grammars that can produce the empty language is designed in this book.

    http://www.amazon.com/New-Kind-Grammars-generative-grammars/dp/1452828687

    By Anonymous Milind "Milz" Bandekar, at 1:28 PM  

  • Oh, those Russians... :-) Greetings from Anastasia! :-)

    By Anonymous Anonymous, at 11:05 PM  

  • In an old book of Nielsson about neural networks this result is used to strengthen the case for neural networks (which are built
    from sum gates and one variable
    sigmoid functions).

    By Anonymous Anonymous, at 6:23 AM  

  • Huh... cool, thanks!

    For which finite collections of sigmoid functions can we densely approximate any continuous function in this manner?

    Another question for the crowds: is there a corresponding result, like Kolmogorov's, for continuous monotone functions?

    By Anonymous Andy D, at 5:18 PM  

  • I was very encouraged to find this site. I wanted to thank you for this special read. I definitely savored every little bit of it and I have bookmarked you to check out new stuff you post.
    I was very encouraged to find this site. I wanted to thank you for this special read. I definitely savored every little bit of it and I have bookmarked you to check out new stuff you post.
    http://www.seotraininginstitute.co.in

    By Blogger Rajesh Kumar, at 4:55 AM  

  • Hey! Coach Factory Online simply wanted to say your website is one of the nicely laid out, most inspirational I have come across in quite a while.

    By Anonymous Coach Factory Online, at 2:51 AM  

  • Stumbled upon this blog today. Nice articles, Andy.

    Seeing the entry on Kolmogorov's theorem I couldn't resist sending you the link to this paper where I first encountered it:
    http://cbcl.mit.edu/people/poggio/journals/girosi-poggio-NeuralComputation-1989.pdf

    By Anonymous Sanjeev Arora, at 11:33 PM  

Post a Comment

<< Home