# 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:

• 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  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, at 11:40 AM

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

By  Anonymous, at 8:36 PM

By  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  Andy D, at 8:51 PM

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

By  khane-libe, at 1:43 AM

• By  オテモヤン, at 10:30 PM

• 沈舟側畔千帆過，病樹前頭萬木春......................................................

By  Anonymous, at 12:58 AM

• 在莫非定律中有項笨蛋定律：「一個組織中的笨蛋，恆大於等於三分之二。」......................................................

By  Anonymous, at 3:21 AM

• 良言一句三冬暖，惡語傷人六月寒。......................................................

By  Anonymous, at 3:23 AM

• 若對自己誠實，日積月累，就無法對別人不忠了。........................................

By  Anonymous, at 6:56 PM

• By  Anonymous, at 9:49 AM

• 知識可以傳授，智慧卻不行。每個人必須成為他自己。...............................................................

By  Anonymous, at 2:42 PM

• 認清問題就等於已經解決了一半的問題。..................................................

By  Anonymous, at 12:15 PM

• 蛛絲馬跡皆學問、落花水面皆文章............................................................

By  Anonymous, at 2:36 PM

• 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, at 1:57 AM

• By  Anonymous, at 6:12 PM

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

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

• 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  Sanjeev Arora, at 11:33 PM