Московское математическое общество, Московский центр непрерывного математического образования, Малый мехмат МГУ

Серия "Библиотека «Математическое просвещение»"

А. Л. Семенов Математика текстов


В брошюре рассматриваются идеи и конструкции, лежащие в основе "математики текстов"; среди примеров ее результатов — несчетност множества последовательностей из нулей и единиц, невозможность создать программу, распознающую самоприменимость программ. Обсуждается важное понятие сложности текста по Колмогорову, позволяющее отличать случайные тексты от неслучайных.
Текст брошюры представляет собой обработанную запись лекции, прочитанной автором 5 декабря 1999 года для участников III Международного математического турнира старшеклассников "Кубок памяти А. Н. Колмогорова" . школьников 8–11 классов. (Запись Е. Н. Осьмовой, обработка Р. М. Кузнеца.)

Оглавление

Введение
1. Логические парадоксы
2. Диагональный метод Кантора
3. Программы
3.1 Самоприменимые программы
3.2 Универсальная программа
4. Cложность текста. Случайные и неслучайные последовательности
5. Решения и комментарии