Теорема Гёделя, наряду с открытием теории относительности, квантовой механики и ДНК, обычно рассматривается как крупнейшее научное достижение ХХ века. Почему? В чем ее суть? Каково ее значение? Эти вопросы в своей лекции раскрывает Алексей Брониславович Сосинский, математик, профессор Независимого московского университета, офицер Ордена академических пальм Французской Республики, лауреат премии Правительства РФ в области образования 2012 года. В частности, были даны несколько разных ее формулировок, описаны три подхода к ее доказательству (Колмогорова, Чейтина и самого Гёделя), и объяснено ее значение для математики, физики, компьютерной науки и философии.

В лекции будут обсуждаться примеры сингулярных (особых) мыльных пленок, натянутых на проволочные контуры сложной формы (узлы, каркас куба и тетраэдра, и др.) Будут проводится демонстрации соответствующих экспериментов с проволоками и мыльным растворам, и на экране будут показаны фотографии и компьютерная графика изображений результатов. Оказывается, что на пленках возникают только два тина особенностей — так называемые “тройные линии” и “шестикрылые бабочки”, удивительным образом совпадающие с особенностями “специальных спайнов” (играющих ключевую роль в работах С. Матвеева и его школы по классификации трехмерных многообразий). Цель лекции — привлечь внимание слушателей к созданию (пока еще не существующей) математической теории сингулярных минимальных поверхностей.

Отрывок из книги нобелевского лауреата Фрэнка Вильчека об идеях красоты и симметрии, лежащих в основе физических концепций.

Пожалуй ни одно другое достижение современной теории сложности вычислений не вызывает такого живого интереса и не менее яростных споров как модель квантовых вычислений. Предметом дискуссии, однако, в основном является возможность физической реализации квантового компьютера, чего мы, к счастью, касаться не будем. Вместо этого мы попробуем разобраться в чисто математических аспектах этой модели и, в частности, постараемся пройти столько из нижеследующего, сколько позволит время: Классические и квантовые схемы; Алгоритм Шора быстрого разложения чисел на множители: основные идеи; Квантовые оракулы и задача о скрытой подгруппе; Алгоритм квантового поиска Гровера.

Как грамотно вычислить значение полинома от многих переменных? Можно, конечно, посчитать по отдельности каждый входящий в него моном и результаты сложить, но нельзя ли придумать способ сэкономить на числе используемых операций хотя бы для некоторых наиболее важных и часто встречающихся полиномов? Изучением таких вопросов как раз и занимается теория алгебраической сложности вычислений. Оказывается, что для некоторых классов полиномов ответ отрицателен, для других он положителен, а в подавляющем большинстве случаев ответ неизвестен. Соответствующие вопросы, открытые в течении нескольких десятилетий, по праву числятся среди наиболее важных, интересных и трудных проблем современной теории сложности.

Попытки дать математические определения понятий формального доказательства, истинности, формализованной деятельности по инструкции привели к построению математической логики и теории алгоритмов — области математики, результаты которой сформировали и продолжают формировать основы информатики и влиять на практическое использование цифровых технологий. Важнейшие результаты данной области, наряду с указанными определениями — это результаты о невозможности, в свою очередь тесно связанные с результатами об универсальности и диагональными конструкциями.

В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть: конструктивный обьект, алгоритм, число шагов алгоритма, вычислимая функция, перечислимое множество, разрешимое множество, сводимость нумераций, главная вычислимая нумерация, вычислимая операция.

Успенский Владимир Андреевич, доктор физико-математических наук, профессор. Летняя школа «Современная математика», г. Дубна, 9 июля 2012 г.; XIV Летняя лингвистическая школа, г. Дубна, «Ратмино», 8-18 июля 2012 г.

Если в качестве значений переменных разрешается брать только элементы носителя, язык называют элементарным языком, или языком первого порядка. Если же в качестве значений переменных разрешается брать также функции и отношения, язык называют языком второго порядка. Выразительные возможности языков первого порядка довольно ограничены. Например, на языке первого порядка можно сообщить, что носитель содержит ровно 17 элементов, но невозможно выразить его конечность. На языке второго порядка выразить конечность носителя возможно. Возникает совершенно естественное недоумение: а зачем тогда пользоваться языками первого порядка с их бедными выразительными средствами, не лучше ли пользоваться языками второго порядка?

Знаменитая Теорема Гёделя о неполноте имеет две версии — синтаксическую (объявленную и доказанную самим Гёделем) и семантическую (чаще всего фигурирующую в популярных рассуждениях о великой Теореме). Семантическая версия утверждает, что какую бы систему формальных доказательств ни придумать, в языке найдутся истинные утверждения, не доказуемые в рамках предложенной системы. Таким образом, семантическая версия исходит из того, что некоторые выражения языка выражают осмысленные утверждения, являющиеся истинными или ложными. Синтаксическая версия не опирается на то, что какие бы то ни было выражения языка имеют какой-то смысл, она смотрит на выражения как на синтаксические конструкции, то есть как на цепочки символов, организованные по определённым правилам.

Целые числа, рациональные, алгебраические… Что дальше (оставаясь в пределах действительных чисел)? Дальше идут вычислимые действительные числа, т.е. такие действительные числа, которые можно в разумном смысле вычислить. «Можно вычислить» означает, что вычисление можно запрограммировать. Мыслимы различные подходы к тому, что именно надо программировать.

Ященко Иван Валериевич, кандидат физико-математических наук. Летняя школа «Современная математика», г. Дубна, 2003 г.

Мы обсудим понятие, которое все используют, но о котором обычно рассказывают по ходу дела — о метрическом пространстве. Постараемся разобрать красивые примеры, обсудить факты и методы применяемые повсюду: от дифференциальных уравнений до теории кодирования и стеганографии — пополнении, принципе сжимающих отображений, теореме Бэра, компактности, теореме Вейерштрасса…

Будет рассказано о понятии, которое все используют, но обычно рассказывают по ходу дела — метрическом пространстве. Будет разобрано много красивых примеров, рассказано о фактах и методах применяемых повсюду: от дифференциальных уравнений до теории кодирования — пополнении, принципе сжимающих отображений, теореме Бэра.

Мы попытаемся рассказать о криптографии — бурно развивающейся прикладной науке, оказывающей огромное влияние на развитие не только техники, но и математики. Особое внимание будет уделено тому, как важно правильно ставить задачи, а также тому, как можно использовать не только достижения, но и “неудачи” математики на практике. В частности, будет рассказано, что такое криптография с открытым ключом и как можно убедить учителя, что ты знаешь ответ на вопрос, так и не дав этого ответа.

В этой лекции мы познакомимся с одним из важнейших понятий топологии — компактностью, начав с обсуждение того, какие же свойства обычного отрезка отвечают за выполнение основных теорем о непрерывных функциях. Будет разобрано много примеров и применений — простых и сложных. В основном, мы будем заниматься метрическими пространствами (определение будет напомнено). Немного позанимаемся и компактностью в топологических пространствах (определение будет дано).

Я буду говорить об одном из самых классических геометрических сюжетов — о кривых на плоскости. Через точку на кривой можно провести «соприкасающуюся окружность»: окружность, проходящую через эту точку, и наилучшим образом приближающую данную кривую. Её радиус это радиус кривизны. Я начну с того, что покажу неожиданное, почти неправдоподобное поведение таких окружностей при движении точки вдоль кривой. Я не буду здесь формулировать никаких утверждений, потому что это испортит сюрприз! Затем, мы перейдём к обсуждению соприкасающихся эллипсов и алгебраических кривых более высокой степени; мы увидим красивые и интересные картины!

При передаче и хранении информация портится (шум в телефонной трубке, ошибки жесткого диска и так далее). Чтобы восстановить исходное сообщение в систему передачи следует ввести избыточность, иными словами, передавать вместо него более длинное закодированное сообщение. Так возникает понятие корректирующего кода (кода, исправляющего ошибки). Математически это приводит к задаче упаковки шаров в конечномерном векторном пространстве над конечным полем. Эта задача, в свою очередь, оказывается в значительной части эквивалентна проблеме расположения точек в проективном пространстве “в наиболее общем положении”. Здесь уже недалеко и до алгебраической геометрии. Конструкцию кодов по алгебраической кривой нетрудно рассказать, когда эта кривая — прямая.

Мы сейчас знаем о строении Вселенной примерно столько же, сколько древние люди знали о поверхности Земли. Точнее, мы знаем, что небольшая часть Вселенной, доступная нашим наблюдениям, устроена так же, как небольшая часть трёхмерного евклидова пространства. Иначе говоря, мы живём на трёхмерном многообразии (3-многообразии). Кругосветным путешествиям и построениям полных атласов может предшествовать априорная классификация маломерных многообразий — вопрос о том, где мы “на самом деле” живём заменяется на вопрос где мы могли бы жить? Эта классификация (требующая некоторых естественных ограничений на многообразия) тривиальна в размерности 1, допускает красивый полный ответ в размерности 2, полученный в XIX веке, и составляет исключительно трудную проблему в размерности 3. В этой проблеме совсем недавно достигнуты замечательные результаты, обзор которых и составляет цель курса.

На Московской математической олимпиаде был предложен «дискретный» вариант теоремы о неподвижной точки внутри замкнутой траектории векторного поля: В некоторых клетках квадрата 20×20 стоит стрелочка в одном из четырёх направлений. На границе квадрата все стрелочки смотрят вдоль границы по часовой стрелке (см. рис.). Кроме того, стрелочки в соседних (возможно, по диагонали) клетках не смотрят в противоположных направлениях. Докажите, что найдётся клетка, в которой стрелочки нет. Разбирая 3–5 решений этой задачи, мы на наглядном уровне увидим теорему Жордана, индекс векторного поля и многое другое.