Математическая логика

О курсе

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

Теория вычислимости тесно переплетается и с математической логикой, особенно с логикой доказательств. Ещё Лейбниц предполагал, что любое рассуждение можно в конечном счёте заменить вычислением. Знаменитая теорема Гёделя о неполноте арифметики в некотором смысле делает невозможным реализацию идеи Лейбница. Теория вычислимости высвечивает глубинные причины этого явления.

В курс также включены два раздела, более близкие к практике. Первый – это лямбда-исчисление, альтернативный способ формализации, что такое программа. Эта наука закладывает основы функционального программирования. Второй – это теория сложности вычислений. На практике неважно, даст ли программа ответ в принципе. Важно, даст ли она его за приемлемое время. В этой теории возникает одна из ключевых открытых проблем современности: равны ли классы P и NP.

Результат

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

О преподавателях

Мусатов Даниил ВладимировичПреподаватель кафедры дискретной математики МФТИ

Входные требования

Все необходимые понятия будут определяться по ходу курса, однако от слушателей предполагается достаточно свободное владение аппаратом дискретной математики и булевой логики. Желателен хотя бы небольшой опыт написания программ.

Содержание курса

Множества и их мощности. Счётные и несчётные множества. Диагональный метод Кантора.
Абстрактное понятие алгоритма. Машины Тьюринга. Счётность множества всех алгоритмов.
Вычислимые функции. Разрешимые и перечислимые множества. Существование невычислимых функций и неразрешимых множеств из соображений мощности.
Неразрешимость проблем самоприменимости и остановки. Теорема Успенского-Райса.
Понятие m-сводимости. Построение неперечислимого множества, дополнение к которому также неперечислимо.
Алгоритмически неразрешимые задачи в комбинаторике и алгебре.
Теорема Клини о неподвижной точке. Существование в любом языке программирования программы, печатающей собственный текст.
Понятие формальной системы доказательств. Аксиомы формальной арифметики.
Теорема Гёделя о неполноте. Существование принципиально непознаваемой программы.
Лямбда-исчисление: синтаксис, приведение к нормальной форме, нумералы Чёрча, реализация простейших функций.
Лямбда-исчисление: комбинатор неподвижной точки и рекурсивное программирование.
Основы теории сложности вычислений: измерение времени работы программы. Классы P и NP. Проблема перебора (равны ли классы P и NP). NP-полные задачи.

Профессии, специальности и направления подготовки	27.00.00 Управление в технических системах 16.00.00 Физико-технические науки и технологии 19.00.00 Промышления экология и биотехнологии 21.00.00 Прикладная геология, горное дело, нефтегазовое дело и геодезия 22.00.00 Технологии материалов 09.00.00 Информатика и вычислительная техника 14.00.00 Ядерная энергетика и технологии 17.00.00 Оружие и системы вооружения 18.00.00 Химические технологии 12.00.00 Фотоника, приборостроение, оптические и биотехнические системы и технологии 29.00.00 Технологии легкой промышленности 25.00.00 Аэронавигация и эксплуатация авиационной и ракетно-космической техники 10.00.00 Информационная безопасность 08.00.00 Техника и технологии строительства 20.00.00 Техносферная безопасность и природообустройство 23.00.00 Техника и технологии наземного транспорта 13.00.00 Электро- и теплоэнергетика 11.00.00 Электроника, радиотехника и системы связи 24.00.00 Авиационная и ракетно-космическая техника 05.00.00 Науки о земле 26.00.00 Техника и технологии кораблестроения и водного транспорта 28.00.00 Нанотехнологии и наноматериалы 07.00.00 Архитектура 15.00.00 Машиностроение
Область деятельности	Инженерное дело, технологии и технические науки Математические и естественные науки
Дата окончания записи	24.12.2021
Трудоёмкость в з.е.	3.0
Количество лекций	13
Дата ближайшего старта	01.09.2021
Дата окончания	24.12.2021
ID курса	19b310c84cc24fdea73695bc2751dc63
К-во обучающихся на версии курса	14632
Язык	Русский
Длительность	13 недель
Сертификат	Есть
Версия	7

О курсе

Результат

О преподавателях

Входные требования

Содержание курса

Рекомендуемые курсы

Рецензии и оценки

Отсутствует текст отзыва.