Читать онлайн «Четыре алгоритимических лица случайности»

Летняя школа «Современная математика» Дубна, июль 2005 В. А. Успенский Четыре алгоритмических лица случайности Москва, 2006 Издательство МЦНМО УДК 510. 5 Проведение летних школ «Современная математика» ББК 22. 12 и издание её материалов было бы невозможно без под- держки Московской городской Думы и Департамента Введение У77 образования г. Москвы, а также без поддержки фонда Если кто-либо скажет нам, что он подбросил «честную» монету два- «Династия», фирмы «НИКС» и корпорации Boeing. дцать раз и, обозначив герб единицей, а решётку — нулём, получил такой Успенский В. А. результат: У77 Четыре алгоритимических лица случайности. — М. : МЦНМО, 10001011101111010000 (I) 2006. — 48 с. ISBN 5-94057-238-3 или такой: 01111011001101110001, (II) Брошюра написана по материалам лекции, прочитанной автором 23 июля 2005 года в летней школе «Современная математика» в Дубне. Она посвящена мы вряд ли будем удивлены. Однако если нам скажут, что результат формализации такого интуитивно ясного термина, как «случайность». В бро- шюре рассматривается четыре разных подхода к этому понятию, основанных бросаний был таким: на характерных свойствах случайных последовательностей: частотоустойчивость, хаотичность, типичность и непредсказуемость. Вводятся важнейшие в теории ал- 00000000000000000000 (III) горитмов понятия перечислимости, вычислимости, энтропии и колмогоровской сложности. С их помощью и можно попытаться ответить на вопрос, с которым или таким: не справляется классическая теория вероятностей: определить, можно ли, напри- 01010101010101010101, (IV) мер, индивидуальную последовательность нулей и единиц считать случайной или нет. В последней главе проводится обобщение понятий частотоустойчивости, хао- мы будем поражены и вообще не поверим или же усомнимся в коррект- тичности, типичности и непредсказуемости на случай вычислимого распределения. Брошюра адресована старшим школьникам и студентам младших курсов. ности эксперимента.