Я вот тут в форуме Алгоритмы

Автор: GhostCoders
Дата: 08.03.20

(тоже на rsdn) написал про ошибку в доказательстве Тьюринга о неразрешимости проблемы остановки.
Но что-то тот форум какой-то вялый.
Может кто-то здесь прокомментирует?

Доказательство Тьюринга.

Сейчас в соседней ветке прочитал про диагональный элемент и неполноту Геделя.
Возможно, это связано (и Тьюринг строил свое доказательство под впечатлением доказательства Геделя о неполноте арифметики Пеано, вводя диагонализатор).
Но тем не менее.

Тут весьма простая ошибка.
Для того чтобы вы лучше это поняли, я представлю вам ошибочное доказательство того,
что уравнение X — 3 = 5 не имеет решений.

"Уравнение X — 3 = 5 не имеет решений. Докажем это от обратного.
Допустим уравнение X — 3 = 5 имеет какое-то решение.
Скажем, что А — это решение уравнения и А <= 0 (А меньше или равно 0).
В таком случае, при максимально возможном значении А в 0 мы имеем:
0 — 3 = 5
-3 = 5
Очевидно, что -3 не равно 5, более того, -3 < 5.
Для значений А меньших 0, значение в левой части уравнения будет, очевидно, еще меньше, чем -3.
Следовательно, уравнение X — 3 = 5 не имеет решений."

Тут раздается возглас с задней парты и ученик спрашивает учителя:
"А для чего мы предположили что А меньше или равно 0? Только для доказательства того, что это уравнение не имеет решений?!"
"Да" — звучит невозмутимый ответ учителя.
Все остальные ученики в классе поворачивают головы назад и недовольно
смотрят на выскочку, который посмелил бросить тень на гениальное доказательство.

Вот таким-же приемом Тьюринг доказывает невозможность существования анализатора.

В случае уравнения, если мы сделали допущение, что А <= 0, и рассмотрели этот случай,
то мы должны рассмотреть случай, когда А > 0.
Мы же этого не сделали.

Тоже самое сделал и Тьюринг.
Фактически он допустил существование анализатора лишь в одной, ему выгодной форме.
И не рассмотрел другие варианты возможного существования анализатора.

Вот эти "странные" допущения Тьюринга:

Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел (N,X), и:

останавливается и возвращает 1, если алгоритм с номером N не останавливается, получив на вход X
не останавливается в противном случае (если алгоритм с номером N останавливается, получив на вход X).

"Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам.
И не рассматривает остальные варианты.

Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.

Это же просто и естественно (особенно для программистов), иметь анализатор,
который возвратит 1 или 0, типа функции is_halt(), которая принимает на вход некую программу.
Если переданная программа может потенциально зависнуть, то сам анализатор должен быть валиден и всегда останавливаться,
возращая 1 или 0.

Надеюсь, я понятно объяснился.

Здравствуйте, GhostCoders, Вы писали:

GC>Я вот тут в форуме Алгоритмы

Автор: GhostCoders
Дата: 08.03.20

(тоже на rsdn) написал про ошибку в доказательстве Тьюринга о неразрешимости проблемы остановки.
GC>Но что-то тот форум какой-то вялый.
GC>Может кто-то здесь прокомментирует?

О, господи. Ну сведением же решается, тот же семестр вуза, где вычислимость проходят.

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

Здравствуйте, GhostCoders, Вы писали:

GC> "Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам.
GC> И не рассматривает остальные варианты.
Это не допущение, а просто такое понятие, которое позволяет выразить в формальном виде проблему остановки.

GC> Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
GC> и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
Да пожалуйста. Но теперь тебе придётся выразить проблему остановки для такого варианта анализатора.

Здравствуйте, deniok, Вы писали:

D>Пусть ваш алгоритм с 0 и 1 на выходе существует. Берем его и строим другой: когда ваш алгоритм завершается с ответом о расходимости входного, запускаем бесконечный цикл. Получаем алгоритм, про который Тьюринг доказал, что его не существует
Я понял вашу мысль.
В таком случае "другой" алгоритм будет всегда гарантировано зависать и ломается доказательство Тьюринга, основанное на противоречии.

Таким образом, "другой" анализатор DA(K, X):
1) Вызывает нормальный анализатор A(K, X) (нормальный анализатор никогда не зависает)
2) Игнорирует результат работы нормального анализатора
3) Тут же зависает (например, abc: goto abc) (безусловно зависает)

То есть "другой" анализатор DA(K, X) — фактически всегда зависает.

Что будет?
Диагонализатор D(X) вызовет "другой" анализатор DA(X, X).
DA(X, X) анализатор вызовет сначала нормальный анализатор A(X, X), для программы X (а X это и есть диагонализатор).
Так как "другой" анализатор DA(K, X) всегда зависает (см. выше), то нормальный анализатор,
проанализировав его возвратит 1.
"Другой" анализатор забивает на результат работы нормального анализатора и зависает.
Таким образом диагонализатор D зависнет.
Вам хотелось зависнуть, вы и написали программу, которая всегда зависает. Какие выводы из этого можно сделать?
Да никаких!
Это первое.

И вообще так поступать нельзя.
Потому что так можно доказать, что любого алгоритма не существует.
Почему? Возьмем алгоритм сортировки.
Построим "другой" алгоритм сортировки, который будет вызывать нормальный алгоритм сортировки и зависать.
Тьюринг доказал, что его не существует. Отсюда вывод, что алгоритмов сортировки не существует.
Это второе.

Третье. Вообще-то, Тьюринг, ничего не доказал.
В том виде анализатор, что предложил Тьюринг, имеет undefined behavour в зависимости от реализации самого анализатора.
Фактически, допустим, если анализатор как-то интерпретирует полученную программу, это фактически означает бесконечную рекурсию
D(X) -> A(X, X) ->интерпретация-> D(X) -> A(X, X) ...

И тут все implementation specific и зависит от того, какой анализатор первым найдет такую бесконечную рекурсию.
Четный или нечетный относительно самого первого вызова.
Если нечетный анализатор найдет зависание (считая, что первый анализатор имеет номер 1 в стеке вызовов), то вся цепочка вернет значение 1:

1 — зависание — 1 — зависание — 1 — зависание — 1(анализатор определил бесконечную рекурсию и возвратил 1)
Если четный — то самый первый анализатор (в стеке вызовов) зависнет, соответственно и вся цепочка зависнет.

зависание — 1 — зависание — 1 — зависание — 1(анализатор определил бесконечную рекурсию и возвратил 1)

То есть, если мы хотели получить неопределенное поведение такого анализатора, то мы его получили. Не более того.
И никаких выводов о существовании или несуществовании алгоритмов сделать нельзя.

Здравствуйте, ·, Вы писали:

GC>> "Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам.
GC>> И не рассматривает остальные варианты.
·>Это не допущение, а просто такое понятие, которое позволяет выразить в формальном виде проблему остановки.
Вот тут интересно. Спасибо. Надо будет ознакомится с этим поподробнее.
Оказывается, тут какое-то формальное определение есть, спасибо.

GC>> Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
GC>> и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
·>Да пожалуйста. Но теперь тебе придётся выразить проблему остановки для такого варианта анализатора.
Интересно, многого я не знал. Но выразить проблему это же не такая большая проблема?
Выразить проблему — это же задача порядка проще?

Кажется, если доказательство Тьюринга — это не доказательство,
то Матиясевич доказал что-то очень близкое, или даже тоже самое.

Он доказал что нельзя создать универсального способа решения Диофантовых уравений,
а это десятая проблема Гильберта.

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

GC>анализатор всегда останавливается
GC>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.

Если анализатор остановится, как ты возобновишь работу анализируемой программы?

Здравствуйте, GhostCoders, Вы писали:

GC>·>Это не допущение, а просто такое понятие, которое позволяет выразить в формальном виде проблему остановки.
GC>Вот тут интересно. Спасибо. Надо будет ознакомится с этим поподробнее.
GC>Оказывается, тут какое-то формальное определение есть, спасибо.
Не совсем прям уж определение, это просто часть док-ва. Т.е. понятие такого анализатора вводится не просто так, а чтобы на его основе построить доказательство теоремы.

GC>>> Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
GC>>> и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
GC>·>Да пожалуйста. Но теперь тебе придётся выразить проблему остановки для такого варианта анализатора.
GC>Интересно, многого я не знал. Но выразить проблему это же не такая большая проблема?
GC>Выразить проблему — это же задача порядка проще?
Ну да, это будет гипотезой. Интереснее эту гипотезу доказать.

Здравствуйте, L.K., Вы писали:

GC>>анализатор всегда останавливается
GC>>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
LK>Если анализатор остановится, как ты возобновишь работу анализируемой программы?
Это какое-то заблуждение и вообще не в тему. Зачем анализатору запускать программу? На то он и Анализатор. Он может просто, например, искать бесконечные циклы.

Здравствуйте, ·, Вы писали:

GC>>Оказывается, тут какое-то формальное определение есть, спасибо.
·>Не совсем прям уж определение, это просто часть док-ва. Т.е. понятие такого анализатора вводится не просто так, а чтобы на его основе построить доказательство теоремы.
Опять не понимаю. Вводится понятие противоречивого анализатора, затем показывается,
что этот противоречиввый анализатор противоречив. После этого делается вывод о невозможности существования любых анализаторов (в том числе и непротиворечивых).
Звучит как: "Докажем что все заборы зеленые. Допустим, что все заборы зеленые.
Ну раз все заборы зеленые, то все заборы зеленые. Что и требовалось доказать — все заборы зеленые".
По-моему мой пример с уравнением X — 3 = 5 показывает, что не любые произвольные допущения мы может делать.

GC>>>> Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
GC>>>> и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
GC>>·>Да пожалуйста. Но теперь тебе придётся выразить проблему остановки для такого варианта анализатора.
GC>>Интересно, многого я не знал. Но выразить проблему это же не такая большая проблема?
GC>>Выразить проблему — это же задача порядка проще?
·>Ну да, это будет гипотезой. Интереснее эту гипотезу доказать.
Доказать, что анализатор существует? Нет, я не знаю существует или нет такой анализатор.
Возможно, что проблема останова действительно неразрешима, только для этого существует (или должно существовать)
другое, правильное доказательство, а не доказательство Тьюринга.

Или я что-то не так понял из написанного вами?

Здравствуйте, GhostCoders, Вы писали:

GC> ·>Не совсем прям уж определение, это просто часть док-ва. Т.е. понятие такого анализатора вводится не просто так, а чтобы на его основе построить доказательство теоремы.
GC> Опять не понимаю. Вводится понятие противоречивого анализатора, затем показывается,
GC> что этот противоречиввый анализатор противоречив.
Ключевое по той ссылке "Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?"
Т.е. сама проблема остановки равносильна конкретно этому анализатору, который сформулирован определённым образом.
А если ты вводишь какие-то другие термины, какие-то другие виды анализаторов, которые делают что-то не то или не так, то скорее всего они не будут равносильны проблеме и смысл затеи теряется.

Здравствуйте, GhostCoders, Вы писали:

Я во всё не вникал, но вот тут очевидная ошибка.

GC> Почему? Возьмем алгоритм сортировки.
GC> Построим "другой" алгоритм сортировки, который будет вызывать нормальный алгоритм сортировки и зависать.
GC> Тьюринг доказал, что его не существует. Отсюда вывод, что алгоритмов сортировки не существует.
Нет, Тьюринг доказал несуществование не любых зависающих алгоритмов, а конкретно Анализатора.
Алгоритм сортировки с зависанием — очевидно существует. Более того, тривиально построить алгоритм, который берёт на вход любой алгоритм и преобразует его в зависающий.

Здравствуйте, GhostCoders, Вы писали:

GC>А эти проблемы (проблема останова, диофантовых уравнений) очень близки.
GC>Возможно, что доказательство, которое завершил Матиясевич и есть настоящее доказательство неразрешимости проблемы останова машины Тьюринга.

Доказательство теоремы Матиясевича (или, как он её называет сам, MRDP-теоремы) показывает, каким образом вопрос об остановке любого алгоритма можно механически переформулировать как вопрос наличия решений у некоторого диофантова уравнения. Если бы мы могли алгоритмически определять наличие решений у любого диофантова уравнения, то мы могли бы использовать этот способ, чтобы алгоритмически решать вопрос об остановке любого алгоритма. А это, как показал Тьюринг, невозможно. Следовательно, заключил Матиясевич, не существует алгоритма, который бы определял наличие решений у любого диофантова уравнения.

Здравствуйте, GhostCoders, Вы писали:

немного вник.
GC> То есть "другой" анализатор DA(K, X) — фактически всегда зависает.
Нет, чтобы получилось что-то интересное, то строить его надо по-другому:
1. Вызывает нормальный анализатор A(K, X)
2. Если результат вызова 0, то возвращается 0
3. Если результат вызова 1, то запускается бесконечный цикл.

Т.е. он не всегда зависает, а тогда и только тогда твой "нормальный" анализатор возвращает ноль.

Здравствуйте, nikov, Вы писали:

N>Доказательство теоремы Матиясевича (или, как он её называет сам, MRDP-теоремы) показывает, каким образом вопрос об остановке любого алгоритма можно механически переформулировать как вопрос наличия решений у некоторого диофантова уравнения. Если бы мы могли алгоритмически определять наличие решений у любого диофантова уравнения, то мы могли бы использовать этот способ, чтобы алгоритмически решать вопрос об остановке любого алгоритма. А это, как показал Тьюринг, невозможно. Следовательно, заключил Матиясевич, не существует алгоритма, который бы определял наличие решений у любого диофантова уравнения.
Интересно. То есть Матиясевич ссылается на доказательство Тьюринга при доказательстве невозможности решений диафантовых уравнений в общем виде?
А то я тут недавно предположил, что если мы найдем способ алгоритмически решать проблему останова, то мы сможем решать любые диафантовы уравнения или доказывать,
что они не имеют решений

Автор: GhostCoders
Дата: 06.03.20

.

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

Здравствуйте, GhostCoders, Вы писали:

GC>Интересно. То есть Матиясевич ссылается на доказательство Тьюринга при доказательстве невозможности решений диафантовых уравнений в общем виде?

Теорема уже была доказана для экспоненциальных диофантовых уравнений (которые помимо сложения и умножения, допускают ещё и возведение в степень, где показатель может содержать переменную). Матиясевич нашёл послединию недостающую часть, показав что даже вопрос о наличии решений для более узкого класса обычных диофантовых уравнений алгоритмически неразрешим. Я советую почитать его книгу, где он, начиная с математики школьного уровня, излагает теорию алгоритмов и диофантовых уравнений, и приводит полное доказательство неразрешимости 10-й проблемы Гильберта:

Ю. В. Матиясевич. Десятая проблема Гильберта. — М.: Наука: Физико-математическая литература, 1993. — (Математическая логика и основания математики; выпуск № 26). — ISBN 502014326X.

Здравствуйте, ·, Вы писали:

·>Т.е. он не всегда зависает, а тогда и только тогда твой "нормальный" анализатор возвращает ноль.
Скопирую свой ответ из другой темы.

Да, уже нашел на английской википедии, функция g().
И получается, что типа Анализатор (is_halt) в таком случае становится "предсказателем" результата работы этой функции g().
(в смысле не возвращаемого значения, а результата зависнет-не зависнет).

И функция g() имеет все способы чтобы "нагадить" Анализатору, сделав все в точности наоборот, вместо зависания, что-нибудь вернуть,
или вместо успешного завершения зависнуть.

Типа человеку предсказали умереть через год, а он заключил пари с предстказателем, так вот этот человек, чтобы выиграть пари, специально прожил до ста лет.
Или наоборот. Предсказатель предсказал, что человек будет жить до 100 лет, а человек, заключил с ним пари, что предсказатель не прав,
и совершил самоубийство на следующий день, чтобы выиграть пари.

Хотя у меня останутся возражения, что, мол, Анализатор возвратил результат функции (зависла или нет)
для того гипотетического запуска (или запуска через интерпретацию) этой функции, который он сделал (или мог гипотетически сделать) сам,
а не того запуска, что запустил его самого.

То есть Тьюринг считает, что алгоритм должен работать строго детерминированно — как в функции в функциональных языках программирования,
а не императивных, с наличием глобальных переменных, и когда результат функции зависит от предыдыщих (разные всякие undefined behaviour)
вызовов. Проще говоря, Тьюринг не допускает дребезга результатов алгоритмов (типа как undefined behaviour).

P.S. Вспомнил про "предсказания", я до этого дошел раньше, когда интересовался темой.
Поэтому и меня тогда и интерес пропал. А сейчас, склероз, опять забыл...

Здравствуйте, GhostCoders, Вы писали:

GC>·>Т.е. он не всегда зависает, а тогда и только тогда твой "нормальный" анализатор возвращает ноль.
GC>Скопирую свой ответ из другой темы.
GC>Да, уже нашел на английской википедии, функция g().
GC>И получается, что типа Анализатор (is_halt) в таком случае становится "предсказателем" результата работы этой функции g().
GC>(в смысле не возвращаемого значения, а результата зависнет-не зависнет).

GC>И функция g() имеет все способы чтобы "нагадить" Анализатору, сделав все в точности наоборот, вместо зависания, что-нибудь вернуть,
GC>или вместо успешного завершения зависнуть.

GC>Типа человеку предсказали умереть через год, а он заключил пари с предстказателем, так вот этот человек, чтобы выиграть пари, специально прожил до ста лет.
GC>Или наоборот. Предсказатель предсказал, что человек будет жить до 100 лет, а человек, заключил с ним пари, что предсказатель не прав,
GC>и совершил самоубийство на следующий день, чтобы выиграть пари.
Ничего не понял. Что за g()? Каким ещё предсказателем?

GC>Хотя у меня останутся возражения, что, мол, Анализатор возвратил результат функции (зависла или нет)
GC>для того гипотетического запуска (или запуска через интерпретацию) этой функции, который он сделал (или мог гипотетически сделать) сам,
GC>а не того запуска, что запустил его самого.
В док-ве теоремы никто ничего запускать не должен и вообще такое понятие не используется. Анализатор не обязан говорить "зависла ли". Он может сказать "зависнет ли". Т.е. условоно говоря... анализатор может быть статическим — смотреть на код и определять его зависаемость без запуска этого кода на выполнение.

GC>То есть Тьюринг считает, что алгоритм должен работать строго детерминированно
Это не Тьюринг считает. Это понятие алгоритма такое. Тьюринг просто доказывает свою теорему об общепринятом понимании понятия "алгоритм", а о твоём личном понимании.

GC>— как в функции в функциональных языках программирования, а не императивных, с наличием глобальных переменных, и когда результат функции зависит от предыдыщих (разные всякие undefined behaviour)
GC>вызовов. Проще говоря, Тьюринг не допускает дребезга результатов алгоритмов (типа как undefined behaviour).
У тебя всё смешалось в кучу. Теорема об алгоритмах. А ЯП это лишь способ записи алгоритмов. Undefined behaviour это не свойство алгоритма, это относится к семантике ЯП, об его спецификации. Т.е. когда человек глядит на код и видит некую конструкцию, но не может сказать как сработает всё окружение начиная от компиляторов, их версий, линковщиков, железа, таймингов и т.п. о том что именно произойдёт.

GhostCoders:

GC>Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается
GC>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.

GC>Это же просто и естественно (особенно для программистов), иметь анализатор,
GC>который возвратит 1 или 0, типа функции is_halt(), которая принимает на вход некую программу.
GC>Если переданная программа может потенциально зависнуть, то сам анализатор должен быть валиден и всегда останавливаться,
GC>возращая 1 или 0.

Как ты определишь, что программа зависла? Может быть просто долго считает?

Читал про такое неформальное доказательство проблемы останова: анализ программы может в той или иной степени абстракции потребовать ее выполнения.
(абстрактное выполнение это выполнение упрощенной программы. Напр. подстановка sign(a)*sign(b) вместо sign(a*b), другие подобные преобразования.)
То есть против конкретного метода анализа останова всегда может быть найден контрпример.

·:

GC>>>анализатор всегда останавливается
GC>>>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
LK>>Если анализатор остановится, как ты возобновишь работу анализируемой программы?
·>Это какое-то заблуждение и вообще не в тему. Зачем анализатору запускать программу? На то он и Анализатор. Он может просто, например, искать бесконечные циклы.

Против любого такого анализатора можно придумать хитрый цикл, который анализатор не находит.
Цикл может зависеть от довольно широкого контекста состояний программы (переменных). Для анализа состояний и понадобится выполнение.