Видео

Первый

12 с лишним минут автор не мог четко сформулировать условия сочетания цветов...

Who find it in RUclips recommendation

И? Где содержание.

Спасибо за интересный семинар! Можно ли скачать презентацию основного доклада?

The text is in russian, the speech is in english, the chairman of the seminar is half-jewish-chinese. And all this happens on the channel "Kolmogorov-Seminar-Moscow" Looks like the end of time has already arrived. And the "композиционная схема - memory-less" at 26:17 is absolutely a gem! Is this a club for mathematicians with bipolar disorder? The form is terrible, but the theme is interesting. Thanks! P.S. But, for God's sake - why did they write the title in russian then?

Нормально рассказал

Подскажите пожалуйста, что можно почитать/посмотреть для осознания происходящего?

понятие случайности и ... вероятности в их реальном аспекте чаще всего объясняют на примере двоичных последовательностей нулей единиц [00:13] скажем если у нас написана последовательность вот такого рода ... то вы все скажете по-видимому ... повторяющиеся группы ... одинаковые [00:35] с другой стороны если я напишу 1000110111... первое впечатление будет что последовательность не закономерна [00:50] ... естественно, что в применении к конечным последовательностям и вообще конечным объектам заданным каким-то описанием конечным это различие может быть только несколько расплывчатым [01:12] естественно, что, например, каждую конечную последовательность можно задать интерполяционной формулой в виде многочлена от номера элемента и так далее [01:24] но тем не менее, мне лично представляется, что математик должен суметь объяснить, в чём эти различия заключаются, именно для больших --- длинных, но конечных --- последовательностей, [01:45] для сложных объектов, описываемых тем или иным конечным аппаратом, а не только ограничиться тем, чтобы определять, что такое случайная бесконечная последовательность... [02:01] такая возможность имеется, можно дать точное определение где появятся некоторые численные оценки степени закономерности, степени случайности конечных объектов ... сколько-нибудь инвариантный характер иметь только в пределе [02:25] задача состоит не только в том, чтобы отличить закономерные объекты от случайных, [02:44] но и среди случайных отделить вероятностно случайные [02:55] от случайного, не поддающегося описанию при помощи теории вероятностей [03:07] я попытаюсь дать такую табличку с тем, чтобы потом заполнить некоторые ответы [03:24] нас, конечно, будет занимать условие ... при которых применима теория вероятностей а следовательно можно обсуждать что такое вероятность [03:43] в наших учебниках и по-видимому во всём мире обычно дают ... начале два определения так называемое классическое определение вероятности и так называемое частотное определение вероятности [04:04] ... недавно совсем появилась в этом году в ... Academic Press очень интересная книжка Файна "ТеориИ вероятностей" [Terrence L. Fine, Theories of Probability. An examination of foundations. Academic Press, 1973] [04:31] здесь описаны разные подходы к обоснованию как математической стороны теории вероятностей, так и, мы бы сказали, применимости теории вероятностей к реальным явлениям. [04:49] Книжка мне очень понравилась. Юрий Владимирович Прохоров был вот сейчас в Таллине привёз эту книжку ... заслуживает всеобщего внимания [05:02] ... в частности имеются главы, посвящённые классическому определению вероятности и частотному определению [05:12] но мне хочется подчеркнуть не ... идею, а то, что на самом деле различие между ними менее глубоко, чем иногда представляют себе [05:25] тут ... кто первый высказал эту идею, что ... представление, частотное представление вероятностей, устойчивость частот, [05:43] прекрасно обосновано с точки зрения классического определения, классического определения, построенного на симметрии [05:54] в чём тут дело? представьте себе, что вы производите N испытаний с s исходами. Пусть ... i-я случайная величина... равняется r с вероятностью p_r, i от единицы до N, r от единицы до s [06:27] в качестве оценок вероятности мы будем употреблять количества... соответствующие числа появлений, значит, в качестве оценок для вектора, если угодно, p_1,...,p_S [06:50] мы будем n делённое на N, где n есть вектор n_1,..., n_s [07:03] но если n_1,...,n_S известны, числа появлений каждого из различных исходов, то остаётся всего скажем M = N!/n_1!...n_S! возможных исходов наших испытаний, [07:34] логарифм (я буду иметь в виду двоичный) от M приблизительно равен N на известное выражение H, известное в теории информации выражение [07:48] H от этого вектора n делённого на N [7:53] и все эти возможные при разных исходах последовательности получат одинаковую вероятность, это достаточные статистики, поэтому знание параметров естественным образом ... [08:10] ну все это, конечно, знают, но что отсюда вытекает? если мы хотим практически сделать какие-нибудь выводы, скажем, относительно разности между частотами в первой половине этого ряда [08:28] и во второй половине то путь через вероятности ... по существу является обходным, лишним [08:40] мы, собственно, вообразили, что есть вероятности p мы оценили их и пытаемся по этим оценкам воспользоваться вероятностными ... для того, чтобы вычислить, скажем, с какой вероятностью получится большое отклонение между частотами в первой половине ряда и во второй половине ряда [9:03] но мы поступим гораздо лучше, если мы всё равно ... если мы непосредственно произведём вычисления, предположив, что все возможные при данном ... исходы ... все равновероятны [09:20] гипотеза, что ... каких-то таинственных вероятностей ... [09:29] конечно, вам покажется, может быть, смелым такое утверждение, что это типичный случай, но мы получим ... достаточно... некоторый общий... достаточно общий аргумент [09:45]

[09:45] для того, чтобы разобраться окончательно в этих вопросах, надо обратиться к недавно сравнительно созданной теории сложности [10:02] ... длинных последовательностей формально конечно любой длины, но теория будет интересна для длинных последовательностей или вообще как говорят конструктивных объектов [10:17] что касается литературы, то я теперь могу сослаться на эту книгу Файна, где очень хорошо то, что было здесь сделано Соломоновым, мною, ещё некоторыми авторами, изложено. [10:36] Из немножко более ранней литературы я буду пожалуй что статью в Успехах математических наук 1970 года Звонкина и Левина [11:00] и потом есть ещё на немецком языке популярная книжка Якобса о машинах Тьюринга и случайных последовательностях [11:12] она есть по-немецки, есть по-русски, я не знаю, может быть, она есть и по-английски: Якобс [11:20] понемножку все эти понятия становятся популярными но всё-таки .. аккуратное изложение начальной статистики(?) нам неудобно ... только, скажем, последовательностями [11:35] нам понадобятся, например, множества, состоящие из конечных последовательностей и так далее. Но относительно области объектов, которые мы будем изучать, \Omega, достаточно нам будет предположить следующее: [11:57] два знака нуль и единица входят в \Omega и если несколько элементов \Omega задано, то последовательность, составленная из них, тоже туда входит. [12:15] Отсюда уже вытекает, что конечные двоичные последовательности туда входят, а конечные двоичные последовательности мы будем просто отождествлять с обычными натуральными числами... обычной записи ... [12:37] и кроме того будет желательно, чтобы множества эле... конечные множества элементов, входящих в \Omega, входили бы в \Omega. Но я произнёс слово, которое ... осталось неясным: конструктивная область объектов [13:00] существенно то, что, скажем, описание множества всегда должно быть таким... простите, что область... все объекты \Omega должны быть занумерованы, иметь натуральные номера, [13:20] причём занумерованы таким образом, что по номерам некоторого конечного числа объектов можно найти номер составленной из них последовательности и номер составленного из них множества. [13:37] наоборот по номерам множества или последовательности можно вычислить определённым алгоритмом номера составляющих элементов [13:50] здесь, когда я говорю "можно вычислить", "алгоритм" и так далее, то имеется в виду, что в применении к номерам объектов дело идёт об определении по аргументу значений частично рекурсивной функции --- будет скрыта в дальнейшем ссылка на теорию рекурсивных функций [14:17] ещё одно маленькое обозначение значит сюда входят заведомо конечные двоичные последовательности b_1,...,b_n нуль или единица [14:36] длина конечной последовательности будет обозначаться l от b_i ну это близкий аналог двоичного логарифма, в дискретной теории более логичный, чем собственно двоичный логарифм [14:49] но то открытие, которое, по-видимому, независимо сделали несколько лиц, в Соединённых Штатах Соломонов, например, очень скромное, но всё-таки важное. ... не помню, в 1965 году, [15:14]

[15:14] заключается вот в чём. Существуют такие асимптотически оптимальные алгоритмы, которые...ну да нет начнёмте с другого [15:31] если имеется какой-нибудь алгоритм A, который позволяет вычислять по двоичной последовательности, называемой нами программой, и элементу, то есть на самом деле... элементу \Omega, то есть на самом деле номеру этого элемента, [15:55] вот если имеется такой алгоритм, который позволяет это делать, иногда безуспешно, так бывает всегда в общих алгоритмах, ... по номерам ... рекурсивным функциям... тогда мы определяем так сложность объекта x из \Omega при заданном объекте y из \Omega относительно алгоритма A: [16:24] минимум длины программы, которая... из которой вместе с y получается x. [16:36] ну или бесконечность, если у нас алгоритм плохой, и не позволяет никогда, ни при какой программе x из y получить [16:48] но нам интересны хорошие алгоритмы и более того, существенна такая теорема, что существует асимптотически оптимальный алгоритм, я буду обозначать буквой U [17:05] так что сложность любого объекта из занумеро... любой заранее заданной конструктивно занумерованной системы конструктивных объектов относительно алгоритма U [17:25] может быть не больше чем относительно любого другого алгоритма плюс константа зависящая только от этого второго алгоритма [17:46] это сравнительно простая теорема по-видимому... по-видимому было важно прийти к этой мысли универсальными алгоритмами логики занимаются много, но универсальными в смысле экономии длины программы они не занимались... [18:06] теперь отсюда вытекает без всякого труда вторая теорема, что если имеются два универсальных алгоритма, то есть два асимптотически оптимальных алгоритма, [18:18] то условная сложность одного объекта относительно другого при этих двух асимптотически оптимальных алгоритмах отличаются не больше чем на константу, зависящую от этих алгоритмов [18:35] ну вот это и даёт возможность сформулировать ряд предложений, скажем, дать ... такие понятия, как дефект случайности который будет ... насколько какой-то конструктивный объект можно считать случайным устроенным без закономерностей [19:07] причём они будут, конечно, зависеть от того ... асимптотически оптимального алгоритма, но это различие можно сделать явно несущественным, когда дело дойдёт до очень больших слов [19:26] значит, таким образом, A это алгоритм, который позволяет... позволяет по двоичной последовательности и конструктивному объекту ... по номеру, если хотите, ну или построить новый объект конструктивный... [19:44] или ничего не даёт здесь берётся минимальная длина такой программы ... [19:55] просто сложность любого объекта можно считать всё равно ... это несущественно... сложность условная при каком-нибудь очень простом заданном объекте [20:10]

[20:10] так... теперь значит дальше я выбираю некоторый один асимптотически оптимальный алгоритм и его обозначение не пишу. [20:21] довольно простые соотношения которые нам дальше понадобятся, собственно: [20:33] сложность пары объектов не превосходит суммы сложности объекта x и условной сложности объекта y при заданном x и плюс некоторое N о котором придётся немножко поговорить [20:58] Грубо говоря, казалось бы, что надо дать программу, которая позволяет построить x, и дать программу, которая позволяет по x построить y. [21:12] Длина этих программ здесь записана, надо их поставить рядом, получится программа, позволяющая найти всю пару с конечной добавочной (?) информацией... [21:31] но это неверно, если вы ставите две двоичные последовательности рядом, количество... будете рассматривать как одну последовательность, ... надо сказать, где кончается первая и где начинается вторая, [21:49] а количество информации, которое для этого нужно, будет ... логарифмом длины последовательности так на самом деле этот добавок он не ограниченной длины, а он будет ... вообще говоря порядка логарифма входящих ... [22:15] ... буду систематически обозначать член, который не больше чем... по порядку не больше чем логарифм... логарифмы входящих в формулу выражений ... грубо это определю ... [22:40] так у нас сейчас времени ... для понимания этого достаточно... логарифм ... достаточно маленький... [22:52] теперь на самом деле вот это неравенство доказывается просто, а на самом деле ... хитроумно доказывается... доказывается и обратное неравенство с таким же дополнительным членом, так что здесь можно написать "равно" [23:15] но обратное доказательство совсем не тривиально, оно было найдено мной и Левиным, независимо, хотя мы вместе работаем, в одной и то же время ... и изложено в ... [23:31] оно не очень просто... из него, между прочим, вытекает симметрия ... количества информации... [23:55] ... естественно считать количеством информации относительно x в y разность между сложностью самого x если его задавать самого по себе минус условная сложность, если y известен. [24:30] так вот оказывается, что действительно количество информации в x относительно y минус количество информации в y относительно x отличаться может только на величину порядка логарифма этих выражений [24:52] из этой формулы уже просто можно вывести, но сама она доказывается довольно хитроумно и более того если бы мы пошли глубже, [25:05] если бы мы учитывали трудность получения информации количество элементарных операций которые нужны для выполнения соответствующих алгоритмов то вероятнее всего, что эта близость информации в x относительно y и в y относительно x вообще не получилась, [25:26] вероятнее всего, то есть она получается так называемым методом перебора, но так как вообще в теории машин Тьюринга и других вычислительных процедур вопрос о неустранимости ... перебора нерешённый вопрос [25:45] то естественно и здесь не решено ... вероятно, не получится, если мы наложим серьёзные ограничения на длительность алгоритма... работы алгоритма