gul_kiev: (buddha eyes)
[personal profile] gul_kiev
Я со школьных лет сталкивался с неразрешимостью некоторых задач, и уровень этой неразрешимости постепенно увеличивался, сейчас приблизившись к границам моего осознания.

Сначала я узнал, что не существует формулы для нахождения корней многочлена степени больше 4. Все мы знаем, как решить квадратное уравнение. Для уравнения третьей степени существует формула Кардано, которую мало кто помнит. Для уравнений четвёртой степени тоже существует формула, которая настолько громоздка, что её никто не только не помнит, но и не применяет. А вот для пятой степени и выше формулы нет. Не просто ещё не придумали, а доказали, что нет. Решения уравнения есть, а формулы для этих решений нет.

Потом обнаружились неберущиеся интегралы. Например, ∫sin(x)dx/x. Нельзя сказать, что не существует функции, производная которой равна sin(x)/x, такая функция существует, но вот записать её в виде формулы никак нельзя (иначе, как этот интеграл). Нерешаемые дифуры. Например, невозможно описать в виде формул траектории движения трёх тел, между которыми есть гравитационное взаимодействие. Хотя, конечно, как-то эти тела летать будут, и это можно численно промоделировать. Странный аттрактор, который к чему-то сходится, но совершенно непонятно, к чему, и как это описать. Решение, с одной стороны, устойчиво, а с другой - не описывается понятными и наглядными графиками, потому и "странный".

Дальше - ещё интереснее.
Одна из проблем Гильберта (десятая), о диофантовых уравнениях. Диофантовы уравнения - это такие, для которых нужно найти решение в целых числах. Например, x²+y²=z² имеет решения (3, 4, 5), (5, 12, 13) и т.д., а вот x3+y3=z3 решений в целых положительных числах не имеет, и это давно доказано. Проблема Гильберта состоит в нахождении универсального алгоритма, позволяющего узнать, имеет ли диофантово уравнение решение или нет. В 70-х годах XX века эта проблема была решена - было доказано, что такого алгоритма не существует. Ещё раз: любое диофантово уравнение либо имеет решение, либо не имеет, но при этом доказано, что не существует алгоритма, позволяющего это узнать.

Недавно узнал про задачу о Геркулесе и гидре. Задача формулируется несложно, и при этом доказано, что она не решается в рамках аксиоматики Пеано (т.е. нашей привычной "арифметики"). Такие утверждения непременно должны быть (это следует из теоремы Гёделя о неполноте), но вот когда явно с таким сталкиваешься - это озадачивает. Как это так - "невозможно решить"? Либо Геркулес убьёт гидру, либо нет. И выйдя за рамки привычной арифметики, применив ординалы (которые требуют трансфинитную индукцию), можно доказать, что Геркулес всё-таки победит. Но без этой самой трансфинитной индукции - увы, ничего доказать нельзя (кроме того, что можно доказать невозможность доказательства).

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

И, что интересно, вполне может оказаться, что тот физический мир, в котором нас с вами угораздило жить, невычислим. В этом предположении не больше мистики, чем в том, что задача трёх тел не решается в виде формулы. Мы привыкли моделировать алгоритмами - ну так мы не в меньшей степени привыкли и формулы записывать. Формулы можно записать не всегда, равным образом и алгоритмически (численно) промоделировать можно не всё.

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

Date: 2015-09-01 09:52 pm (UTC)
From: [identity profile] ifreedom.livejournal.com
Спасибо, хороший пост. Я еще вспомнил про невыдимые утверждения, и вообще полное погружение.

Кстати, статья как раз в тему твоего последнего вопроса, если не видел - http://geektimes.ru/post/145929/. Я не совсем согласен с практической стороной "Если же для физически реализованного алгоритмического процесса «входной лентой» будет также вся Вселенная" реализации ИИ, но все равно интересно.

Date: 2015-09-02 04:10 am (UTC)
From: [identity profile] vurdy.livejournal.com
"Нельзя объять необъятное" (ц) Козьма Прутков
"Если нельзя объять необъятное, то можно ли это сделать по частям?" (ц) "Клуб "ДС" "ЛГ"

Date: 2015-09-05 01:43 am (UTC)
From: [identity profile] antonreshin.livejournal.com
Вообще-то интегрально-дифференциальное исчисление так и выглядит.

Date: 2015-09-02 07:14 pm (UTC)
From: [identity profile] evgeniirudnyi.livejournal.com
Доказательсто, что идеального алгоритма не существует, означает, является само по себе полноценным знанием. Оно в определенной степени отрицает тезис о непозоваемости мира. Вот, ведь можно абсолютно точно сказать, что такой идеальный алгоритм невозможен. Человеческий разум оказался способен даже на такое.

Date: 2015-09-05 01:40 am (UTC)
From: [identity profile] antonreshin.livejournal.com
Рекурсивная софистика? Вы сами-то поняли, чего написали? Для вас любое доказательство непознаваемости мира будет уже его познаваемостью, что рекурсивно. А без доказательств вы мне, как агностику, просто не поверите. Удобная позиция у вас, однако!
Edited Date: 2015-09-05 01:55 am (UTC)

Date: 2015-09-05 07:17 am (UTC)
From: [identity profile] evgeniirudnyi.livejournal.com
Извините, я не совсем понял ваш ответ. Я попробую сформулировать вашу позиция своими словами. Если я ошибся, поправьте пожалуйста.

1) Мир непознаваем.
2) Непознаваемость мира можно доказать.
3) Доказательство о непозноваемости мира подтверждает непозноваемость мира.

Правильно я вас понял?

Date: 2015-09-05 03:23 pm (UTC)
From: [identity profile] antonreshin.livejournal.com
Я не писал, что можно доказать. Лично мне доказательства не нужны. Зато они нужны вам. Но как только вы их получите, вы будете утверждать, что раз есть доказательства непознаваемости, то мир познаваем.

Date: 2015-09-05 05:14 pm (UTC)
From: [identity profile] evgeniirudnyi.livejournal.com
В этом состоит вопрос: можно ли совместить позицию о непозноваемости мира с существованием доказательства о непозноваемости мира.

Date: 2015-09-05 05:51 pm (UTC)
From: [identity profile] antonreshin.livejournal.com
Это не моя позиция, а ваша. Мне никаких доказательств не нужно. Не создавайте себе химер!

Date: 2015-09-05 07:42 pm (UTC)
From: [identity profile] evgeniirudnyi.livejournal.com
Извините, но вы же выше написали "Рекурсивная софистика? Вы сами-то поняли, чего написали?". Не могли бы вы пожалуйста пояснить, что вы хотели этим сказать?

Date: 2015-09-05 08:03 pm (UTC)
From: [identity profile] antonreshin.livejournal.com
Рекурсивность вашей софистики заключается в том, что ваша логика идёт в обратную сторону, и сама в себе заворачивается: "Докажите мне, что мир непознаваем, и я опровергну вас вашими же доказательствами!" (Это ваша позиция.) А вот мне никаких доказательств непознаваемости мира не нужно! Они нужны только вам, да и то, только чтобы их опровергнуть.

Date: 2015-09-06 06:40 am (UTC)
From: [identity profile] evgeniirudnyi.livejournal.com
Я просто пытаюсь рассуждать логически. Ваши же ответы показывают, что логика вам неинтересна.

Date: 2015-09-06 10:44 pm (UTC)
From: [identity profile] antonreshin.livejournal.com
Про вашу логику я вам уже написал. А непознаваемое вообще никакой логике не подчиняется, поэтому применять её к непознаваемому просто бессмысленно. "Наука - это путь от одного заблуждения к другому." (С) мой.

Кстати, а вам не приходило в голову, что если бы мир был познаваем, то он был бы давно уже познан, и на этом развитие не только науки, а и всего человечества остановилось бы?
Edited Date: 2015-09-06 10:56 pm (UTC)

Date: 2015-09-07 05:26 pm (UTC)
From: [identity profile] evgeniirudnyi.livejournal.com
Если логику исключить из рассмотрения, то проблем не будет.

Date: 2015-12-21 10:02 pm (UTC)
livelight: (lightning)
From: [personal profile] livelight
Дон Хуан категорически заявляет, что не всё возможно объять Тоналем.

А для того, что им объять возможно, но не получается при уже придуманном базисе (например, взяли несколько функций, объявили их "элементарными", взяли способы допустимой суперпозиции функций и с удивлением обнаружили, что в этом базисе ∫sin(x)dx/x невыразимо) -- ну так фигня вопрос, базис можно ж и расширить. А потом ещё и ещё, пока старина Гёдель не погрозит нам ехидно пальцем.

September 2017

S M T W T F S
     12
3456789
10111213 141516
17181920212223
24252627282930

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 22nd, 2017 02:42 am
Powered by Dreamwidth Studios