### 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...]

"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."

-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: general math

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

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

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

オナニー

逆援助

SEX

フェラチオ

ソープ

逆援助

出張ホスト

手コキ

おっぱい

フェラチオ

中出し

セックス

デリヘル

包茎

逆援

性欲

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

ut中部人聊天聊天尋夢080中聊天室南部聊天友聊天室免費色情影片看免費色遊戲網免費色請影片免費免下載ava片線上看免費免下載a片免費免會員色情影片免費男女做愛影片免費男女影片免費色情狂看免費色情成影片免費色情卡通線上看免費成年人短片免費成年人線上短片免費成年人線上影片免費成短片免費色小遊戲免費色文章免費色片分享免費色片電影直播免費色片線上直播免費色卡通動畫短片免費色卡通漫畫免費色動畫免費色情片圖片免費男片小遊戲下載區視訊美女館色情小說美女

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 Milind "Milz" Bandekar, at 1:28 PM

Learning makes life sweet.............................................................

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.

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

Post a Comment

<< Home