|
||
|
|
||
| Главная ≫ Инфотека ≫ Математика ≫ Видео ≫ Невычислимость, неразрешимость, недоказуемость (Тюринг → Колмогоров → Чейтин → Гёдель) // Алексей Сосинский |
Невычислимость, неразрешимость, недоказуемость (Тюринг → Колмогоров → Чейтин → Гёдель)Алексей Сосинский
Курс занятий посвящен тому, что в математике сделать нельзя. Но речь пойдет не о запрещенных действиях (типа деления на ноль или квадратуры круга), а об отсутствии общих методов для решения некоторых широких классов задач. Начиная от определения вычислимой функции (через машину Тюринга), мы узнаем про существование универсальной вычислимой функции, и как следствие – о существовании не вычислимых функций. Отсюда мы поймем, какие задачи никакой компьютер (даже сколь угодно мощный) решить не может в принципе. Затем мы выясним, в каком смысле последовательность 100110111010010010101100101101010011100010010010010010000111110110010100001111100 «сложней», чем последовательность 10101010101010101010101010101010101010101010101010101010101010101010101010101010, т. е. определим «Колмогоровскую сложность» и изучим ряд ее «нехороших» свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте – одного из самых значительных научных открытий ХХ-го века. А если останется время (боюсь, что вряд ли это произойдет), я расскажу как сложность связана с энтропией и энергией в статистической физике. Программа курса: 1. Вычислимые и не вычислимые функции. 2. Разрешимые и неразрешимые множества. Примеры алгоритмически неразремимых проблем. 3. Колмогоровская сложность. 4. Первая теорема Гёделя о неполноте и ее прикладной смысл. Доказательство теоремы Гёделя методом Чейтина (через Колмогоровскую сложность). Курс будет трудным, но никаких предварительных специальных знаний не требуется – он будет доступен школьникам. Сосинский Алексей Брониславович, кандидат физико-математических наук. Летняя школа «Современная математика», г. Дубна. 20–28 июля 2014 г.
ТегиПохожее
|
Эта книга предназначена для широкого круга читателей, желающих узнать больше об окружающем нас мире и о самих себе. Автор, известный ученый и популяризатор науки, с необычайной ясностью и глубиной объясняет устройство Вселенной, тайны квантового мира и генетики, эволюцию жизни и показывает важность математики для познания всей природы и человеческого разума в частности.
Знаменитая Теорема Гёделя о неполноте имеет две версии — синтаксическую (объявленную и доказанную самим Гёделем) и семантическую (чаще всего фигурирующую в популярных рассуждениях о великой Теореме). Семантическая версия утверждает, что какую бы систему формальных доказательств ни придумать, в языке найдутся истинные утверждения, не доказуемые в рамках предложенной системы. Таким образом, семантическая версия исходит из того, что некоторые выражения языка выражают осмысленные утверждения, являющиеся истинными или ложными. Синтаксическая версия не опирается на то, что какие бы то ни было выражения языка имеют какой-то смысл, она смотрит на выражения как на синтаксические конструкции, то есть как на цепочки символов, организованные по определённым правилам.
В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть: конструктивный обьект, алгоритм, число шагов алгоритма, вычислимая функция, перечислимое множество, разрешимое множество, сводимость нумераций, главная вычислимая нумерация, вычислимая операция.
Теорема Гёделя, наряду с открытием теории относительности, квантовой механики и ДНК, обычно рассматривается как крупнейшее научное достижение ХХ века. Почему? В чем ее суть? Каково ее значение? Эти вопросы в своей лекции раскрывает Алексей Брониславович Сосинский, математик, профессор Независимого московского университета, офицер Ордена академических пальм Французской Республики, лауреат премии Правительства РФ в области образования 2012 года. В частности, были даны несколько разных ее формулировок, описаны три подхода к ее доказательству (Колмогорова, Чейтина и самого Гёделя), и объяснено ее значение для математики, физики, компьютерной науки и философии.
Всякая надежда на создание единой математической теории, амбициозного проекта, который был предложен математиком Давидом Гильбертом в 19 веке и продолжил существовать, поддерживаемый многими, в 20 столетии, рухнула. Основы математики были далеко не столь надежными, как того хотел бы Гильберт. А Гëдель своими теоремами ясно продемонстрировал, что любая система аксиом, какой бы обширной она ни была, уязвима для возникновения невосполнимых пробелов. Попытки же восполнить их созданием более полной системы породили бы только бóльшее количество утверждений без доказательств — так что и тут возникнет необходимость в усовершенствовании системы, и так далее до бесконечности. И случилось нечто странное: математики решили не обращать на это внимания. Они посчитали, что неполнота систем не имеет непосредственного влияния на их работу.| Главная ≫ Инфотека ≫ Математика ≫ Видео ≫ Невычислимость, неразрешимость, недоказуемость (Тюринг → Колмогоров → Чейтин → Гёдель) // Алексей Сосинский |
|
[time: 10 ms; queries: 7]
22 Дек 2024 05:21:26 GMT+3 |