Неразрешимость
Я со школьных лет сталкивался с неразрешимостью некоторых задач, и уровень этой неразрешимости постепенно увеличивался, сейчас приблизившись к границам моего осознания.
Сначала я узнал, что не существует формулы для нахождения корней многочлена степени больше 4. Все мы знаем, как решить квадратное уравнение. Для уравнения третьей степени существует формула Кардано, которую мало кто помнит. Для уравнений четвёртой степени тоже существует формула, которая настолько громоздка, что её никто не только не помнит, но и не применяет. А вот для пятой степени и выше формулы нет. Не просто ещё не придумали, а доказали, что нет. Решения уравнения есть, а формулы для этих решений нет.
Потом обнаружились неберущиеся интегралы. Например, ∫sin(x)dx/x. Нельзя сказать, что не существует функции, производная которой равна sin(x)/x, такая функция существует, но вот записать её в виде формулы никак нельзя (иначе, как этот интеграл). Нерешаемые дифуры. Например, невозможно описать в виде формул траектории движения трёх тел, между которыми есть гравитационное взаимодействие. Хотя, конечно, как-то эти тела летать будут, и это можно численно промоделировать. Странный аттрактор, который к чему-то сходится, но совершенно непонятно, к чему, и как это описать. Решение, с одной стороны, устойчиво, а с другой - не описывается понятными и наглядными графиками, потому и "странный".
Дальше - ещё интереснее.
Одна из проблем Гильберта (десятая), о диофантовых уравнениях. Диофантовы уравнения - это такие, для которых нужно найти решение в целых числах. Например, x²+y²=z² имеет решения (3, 4, 5), (5, 12, 13) и т.д., а вот x3+y3=z3 решений в целых положительных числах не имеет, и это давно доказано. Проблема Гильберта состоит в нахождении универсального алгоритма, позволяющего узнать, имеет ли диофантово уравнение решение или нет. В 70-х годах XX века эта проблема была решена - было доказано, что такого алгоритма не существует. Ещё раз: любое диофантово уравнение либо имеет решение, либо не имеет, но при этом доказано, что не существует алгоритма, позволяющего это узнать.
Недавно узнал про задачу о Геркулесе и гидре. Задача формулируется несложно, и при этом доказано, что она не решается в рамках аксиоматики Пеано (т.е. нашей привычной "арифметики"). Такие утверждения непременно должны быть (это следует из теоремы Гёделя о неполноте), но вот когда явно с таким сталкиваешься - это озадачивает. Как это так - "невозможно решить"? Либо Геркулес убьёт гидру, либо нет. И выйдя за рамки привычной арифметики, применив ординалы (которые требуют трансфинитную индукцию), можно доказать, что Геркулес всё-таки победит. Но без этой самой трансфинитной индукции - увы, ничего доказать нельзя (кроме того, что можно доказать невозможность доказательства).
Существуют другие задачи, для которых доказана алгоритмическая неразрешимость. Например, невозможно алгоритмически определить, возможно ли замостить плоскость фигурками полиомино (т.е. состоящими из одинаковых квадратиков, как в тетрисе). В некоторых случая возможно, в некоторых нет, а в общем случае - неразрешимо.
И, что интересно, вполне может оказаться, что тот физический мир, в котором нас с вами угораздило жить, невычислим. В этом предположении не больше мистики, чем в том, что задача трёх тел не решается в виде формулы. Мы привыкли моделировать алгоритмами - ну так мы не в меньшей степени привыкли и формулы записывать. Формулы можно записать не всегда, равным образом и алгоритмически (численно) промоделировать можно не всё.
А вот можно ли понять, осознать и предсказать при помощи человеческого разума те процессы, которые заведомо невозможно промоделировать на обычном компьютере - вопрос интересный, мне ответ неизвестен.
Сначала я узнал, что не существует формулы для нахождения корней многочлена степени больше 4. Все мы знаем, как решить квадратное уравнение. Для уравнения третьей степени существует формула Кардано, которую мало кто помнит. Для уравнений четвёртой степени тоже существует формула, которая настолько громоздка, что её никто не только не помнит, но и не применяет. А вот для пятой степени и выше формулы нет. Не просто ещё не придумали, а доказали, что нет. Решения уравнения есть, а формулы для этих решений нет.
Потом обнаружились неберущиеся интегралы. Например, ∫sin(x)dx/x. Нельзя сказать, что не существует функции, производная которой равна sin(x)/x, такая функция существует, но вот записать её в виде формулы никак нельзя (иначе, как этот интеграл). Нерешаемые дифуры. Например, невозможно описать в виде формул траектории движения трёх тел, между которыми есть гравитационное взаимодействие. Хотя, конечно, как-то эти тела летать будут, и это можно численно промоделировать. Странный аттрактор, который к чему-то сходится, но совершенно непонятно, к чему, и как это описать. Решение, с одной стороны, устойчиво, а с другой - не описывается понятными и наглядными графиками, потому и "странный".
Дальше - ещё интереснее.
Одна из проблем Гильберта (десятая), о диофантовых уравнениях. Диофантовы уравнения - это такие, для которых нужно найти решение в целых числах. Например, x²+y²=z² имеет решения (3, 4, 5), (5, 12, 13) и т.д., а вот x3+y3=z3 решений в целых положительных числах не имеет, и это давно доказано. Проблема Гильберта состоит в нахождении универсального алгоритма, позволяющего узнать, имеет ли диофантово уравнение решение или нет. В 70-х годах XX века эта проблема была решена - было доказано, что такого алгоритма не существует. Ещё раз: любое диофантово уравнение либо имеет решение, либо не имеет, но при этом доказано, что не существует алгоритма, позволяющего это узнать.
Недавно узнал про задачу о Геркулесе и гидре. Задача формулируется несложно, и при этом доказано, что она не решается в рамках аксиоматики Пеано (т.е. нашей привычной "арифметики"). Такие утверждения непременно должны быть (это следует из теоремы Гёделя о неполноте), но вот когда явно с таким сталкиваешься - это озадачивает. Как это так - "невозможно решить"? Либо Геркулес убьёт гидру, либо нет. И выйдя за рамки привычной арифметики, применив ординалы (которые требуют трансфинитную индукцию), можно доказать, что Геркулес всё-таки победит. Но без этой самой трансфинитной индукции - увы, ничего доказать нельзя (кроме того, что можно доказать невозможность доказательства).
Существуют другие задачи, для которых доказана алгоритмическая неразрешимость. Например, невозможно алгоритмически определить, возможно ли замостить плоскость фигурками полиомино (т.е. состоящими из одинаковых квадратиков, как в тетрисе). В некоторых случая возможно, в некоторых нет, а в общем случае - неразрешимо.
И, что интересно, вполне может оказаться, что тот физический мир, в котором нас с вами угораздило жить, невычислим. В этом предположении не больше мистики, чем в том, что задача трёх тел не решается в виде формулы. Мы привыкли моделировать алгоритмами - ну так мы не в меньшей степени привыкли и формулы записывать. Формулы можно записать не всегда, равным образом и алгоритмически (численно) промоделировать можно не всё.
А вот можно ли понять, осознать и предсказать при помощи человеческого разума те процессы, которые заведомо невозможно промоделировать на обычном компьютере - вопрос интересный, мне ответ неизвестен.