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

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