Здравствуйте, ·, Вы писали:
·>Правда память под состояния у тебя закончится гораздо раньше.
Это же классика — алгоритм черепахи и зайца. Достаточно хранить только два состояния.
Запускаем две машинки: медленную и быструю. Если есть цикл — то быстрая врежется состоянием в состояние медленной.
Re[2]: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Здравствуйте, L.K., Вы писали:
GC>>анализатор всегда останавливается GC>>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа. LK>Если анализатор остановится, как ты возобновишь работу анализируемой программы?
Это какое-то заблуждение и вообще не в тему. Зачем анализатору запускать программу? На то он и Анализатор. Он может просто, например, искать бесконечные циклы.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[4]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, GhostCoders, Вы писали:
GC>Интересно. То есть Матиясевич ссылается на доказательство Тьюринга при доказательстве невозможности решений диафантовых уравнений в общем виде?
Теорема уже была доказана для экспоненциальных диофантовых уравнений (которые помимо сложения и умножения, допускают ещё и возведение в степень, где показатель может содержать переменную). Матиясевич нашёл послединию недостающую часть, показав что даже вопрос о наличии решений для более узкого класса обычных диофантовых уравнений алгоритмически неразрешим. Я советую почитать его книгу, где он, начиная с математики школьного уровня, излагает теорию алгоритмов и диофантовых уравнений, и приводит полное доказательство неразрешимости 10-й проблемы Гильберта:
Ю. В. Матиясевич. Десятая проблема Гильберта. — М.: Наука: Физико-математическая литература, 1993. — (Математическая логика и основания математики; выпуск № 26). — ISBN 502014326X.
Здравствуйте, GhostCoders, Вы писали:
GC>В данный момент я не обладаю детальными знаниями о теоремах Геделя, поэтому надо будет подтянуть.
Очень советую почитать на эту тему:
Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов, выложены авторами в свободный доступ: https://www.mccme.ru/free-books, ftp://ftp.mccme.ru/users/shen/logic
• Часть 1. Начала теории множеств
• Часть 2. Языки и исчисления
• Часть 3. Вычислимые функции
Torkel Franzén, Inexhaustibility: A Non-Exhaustive Treatment. Wellesley, Massachusetts: A K Peters, Ltd. 2004. Lecture Notes in Logic, #16, Association for Symbolic Logic. ISBN 1-56881-174-8
Pavel Pudlák, Logical foundations of mathematics and computational complexity. A gentle introduction, Springer 2013. Springer Monographs in Mathematics. ISBN 978-3-319-00118-0
Все они излагают материал очень подробно, изначально требуя лишь понимания математики на школьном уровне.
GC>P.S.: Я так понимаю, что вы профессионально этим занимаетесь? Статические анализаторы какие-то строите?
Да, я занимался компиляторами и статическим анализом раньше. Последнее время я работаю над построением индексов и поиском в документах.
Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
(тоже на 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.
Здравствуйте, Bill Baklushi, Вы писали:
BB>·>Это какое-то заблуждение и вообще не в тему. Зачем анализатору запускать программу? На то он и Анализатор. Он может просто, например, искать бесконечные циклы. BB> Против любого такого анализатора можно придумать хитрый цикл, который анализатор не находит.
А с чего ты это взял? Мамой клянёшься? Собственно Тьюринг это и сделал — он формально доказал теоретическую невозможность построения такого умного анализатора, который распознает _любой_ хитрый цикл. ИЧСХ, распознавать огромное число бесконечных циклов вполне таки возможно.
Скажем, вот есть проблема четырёх красок. Сто лет пытались доказать. Выяснилось, что есть всего порядка тысячи вариантов карт и для каждого из них отдельно доказывается, притом только с помощью компьютера, иначе нереально. Так могло получиться и с проблемой останова, если бы не было док-ва Тьюринга. Ведь ничего не мешало существовать очень большому, но конечному набору видов циклов, например.
BB>Цикл может зависеть от довольно широкого контекста состояний программы (переменных). Для анализа состояний и понадобится выполнение.
Ты просто подгоняешь свои рассуждения под уже известный ответ.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
(тоже на rsdn) написал про ошибку в доказательстве Тьюринга о неразрешимости проблемы остановки. GC>Но что-то тот форум какой-то вялый. GC>Может кто-то здесь прокомментирует?
Я професионально занимаюсь компиляторами и мой коментарий следующий: на данный момент эта задача находится на грани человеского познания.
Существующие материалы часто оперируют формулировкой из ряда "нетривиальные циклы (неразрешимо)". И тем самым замыливают возможность детального рассмотрения нетривиальности в течении последних 70-ти лет.
Однако, если убрать из формулировки машины Тьюринга возможность самомодификации кода (архитектура фон Неймана), и урезать ее до Гарвардской архитектуры, то интуитивно задача останова могла бы иметь решение с помошью анализа графов потока управления и данных с выводом граничных значений в местах ветвлений.
И вот здесь наступает интересный момент. Из-за того, что даже Гарвардская архитектура обладает Тьюринговой полнотой, программа написанная в ее рамках может воспроизводить любую другую архитекуру, в том числе и архитектуру фон Неймана. И вот здесь будут обрываться попытки дальнейшего анализа привычными средствами, т.к. для анализа кода "виртуализированной" программы анализатор потоков управления и данных должен уметь переходить в домен только что построенных самой же программой "примитивов", что выглядит на сегодняшний день невероятным.
Эта и есть та самая граница научного познания.
Если вы спросите меня возможно ли это — то интуитивно я вам скажу, что может быть. Когда это могло бы произойти — через 50 лет как мимнимум, а может и через 200.
Re: Ошибка в доказательстве Тьюринга о неразрешимости пробле
Возможно, конкретный ответ на заданный вопрос уже был дан выше (всю тему не читал, каюсь), но тем не менее.
Для ответа на вопрос, удобно рассмотреть проблему остановки в терминах множеств. Теорема Тьюринга, по сути, доказывает неразрешимость множества алгоритмов, останавливающихся на заданном наборе входных данных, являясь при этом частным случаем теоремы Райса-Успенского, которая доказывает ровно то же самое, но для любого нетривиального свойства, а не только остановки.
GC>"Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам. GC>И не рассматривает остальные варианты.
Это называется "полуразрешающий алгоритм". Если для элементов множества существует такой алгоритм, то оно является перечислимым.
GC>Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается GC>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
А это называется "разрешающий алгоритм". Множества, для элементов которого такой алгоритм существует, являются разрешимыми.
Диагональный аргумент, заимствованный Тьюрингом у Гёделя (который, в свою очередь позаимствовал его у Кантора) доказывает неперечислимость множества алгоритмов, останавливающихся на заданном наборе данных. По теореме Поста, для того, чтобы оно было разрешимым, его дополнение (т.е. множество всех алгоритмов, зависающих на заданном наборе данных) должно быть перечислимым. Но с помощью того же самого диагонального аргумента можно показать неперечислимость также и дополнения, следовательно рассматриваемое изначально множество является неразрешимым.
Иными словами, "остальные варианты" (включая и упомянутый всюду определённый анализатор, который всегда останавливается) являются лишь частными случаями варианта, рассмотренного Тьюрингом, хотя это сходу, действительно, не так уж и очевидно.
Здравствуйте, GhostCoders, Вы писали:
GC>Сейчас в соседней ветке прочитал про диагональный элемент и неполноту Геделя. GC>Возможно, это связано (и Тьюринг строил свое доказательство под впечатлением доказательства Геделя о неполноте арифметики Пеано, вводя диагонализатор).
Конечно, это связано. Если бы мы могли алгоритмически решать проблему остановки, мы могли бы написать алгоритм, который перебирает все доказательства в арифметике Пеано (или любой другой теории с рекурсивно перечислимыми теоремами), и останавливается как только находит доказательство противоречия. Затем, используя наш способ, мы определили бы, останавливается этот алгоритм или нет, что позволило бы нам узнать, является ли теория непротиворечивой. Но вопрос остановки алгоритма можно выразить в языке арифметики Пеано, и, более того, если алгоритм останавливается и выдаёт определённый результат, то это всегда тривиально доказуемо в арифметике Пеано. Это значит, что если бы существовал способ алгоритмически решать проблему остановки, то арифметика Пеано могла бы доказывать собственную непротиворечивость, что, как мы знаем из теоремы Гёделя, невозможно сделать в непротиворечивой теории. По сути, эти два результата эквивалентны.
Re[3]: Ошибка в доказательстве Тьюринга о неразрешимости про
немного вник. GC> То есть "другой" анализатор DA(K, X) — фактически всегда зависает.
Нет, чтобы получилось что-то интересное, то строить его надо по-другому:
1. Вызывает нормальный анализатор A(K, X)
2. Если результат вызова 0, то возвращается 0
3. Если результат вызова 1, то запускается бесконечный цикл.
Т.е. он не всегда зависает, а тогда и только тогда твой "нормальный" анализатор возвращает ноль.
Здравствуйте, ·, Вы писали:
GC>>Оказывается, тут какое-то формальное определение есть, спасибо. ·>Не совсем прям уж определение, это просто часть док-ва. Т.е. понятие такого анализатора вводится не просто так, а чтобы на его основе построить доказательство теоремы.
Опять не понимаю. Вводится понятие противоречивого анализатора, затем показывается,
что этот противоречиввый анализатор противоречив. После этого делается вывод о невозможности существования любых анализаторов (в том числе и непротиворечивых).
Звучит как: "Докажем что все заборы зеленые. Допустим, что все заборы зеленые.
Ну раз все заборы зеленые, то все заборы зеленые. Что и требовалось доказать — все заборы зеленые".
По-моему мой пример с уравнением X — 3 = 5 показывает, что не любые произвольные допущения мы может делать.
GC>>>> Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается GC>>>> и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа. GC>>·>Да пожалуйста. Но теперь тебе придётся выразить проблему остановки для такого варианта анализатора. GC>>Интересно, многого я не знал. Но выразить проблему это же не такая большая проблема? GC>>Выразить проблему — это же задача порядка проще? ·>Ну да, это будет гипотезой. Интереснее эту гипотезу доказать.
Доказать, что анализатор существует? Нет, я не знаю существует или нет такой анализатор.
Возможно, что проблема останова действительно неразрешима, только для этого существует (или должно существовать)
другое, правильное доказательство, а не доказательство Тьюринга.
Здравствуйте, GhostCoders, Вы писали:
GC>А эти проблемы (проблема останова, диофантовых уравнений) очень близки. GC>Возможно, что доказательство, которое завершил Матиясевич и есть настоящее доказательство неразрешимости проблемы останова машины Тьюринга.
Доказательство теоремы Матиясевича (или, как он её называет сам, MRDP-теоремы) показывает, каким образом вопрос об остановке любого алгоритма можно механически переформулировать как вопрос наличия решений у некоторого диофантова уравнения. Если бы мы могли алгоритмически определять наличие решений у любого диофантова уравнения, то мы могли бы использовать этот способ, чтобы алгоритмически решать вопрос об остановке любого алгоритма. А это, как показал Тьюринг, невозможно. Следовательно, заключил Матиясевич, не существует алгоритма, который бы определял наличие решений у любого диофантова уравнения.
Re[6]: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Здравствуйте, GhostCoders, Вы писали:
GC>·>А с чего ты это взял? Мамой клянёшься? Собственно Тьюринг это и сделал — он формально доказал теоретическую невозможность построения такого умного анализатора, GC>Вы оба доказываете друг другу одно и тоже — то что Анализатор нельза построить, ошибочно предполагая, что собеседник придерживается противоположного мнения.
Он перепутал причину со следствием. Он утверждает, что "Против любого такого анализатора можно придумать хитрый цикл" — но это следствие теоремы остановки, а не её обоснование. Т.е. иначе говоря, хитрые циклы можно придумывать потому что Анализатор невозможен, а не то что хитрость циклов каким-то образом обосновывает невозможность Анализатора.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[5]: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Здравствуйте, σ, Вы писали:
σ>Но не всегда верно, а именно, в Началах теории множеств приводится широко распространённое неверное доказательство теоремы о том, что в каждом бесконечном множестве содержится счётное подмножество.
Ну они предупреждают, что излагают "наивную" теорию множеств, просто чтобы дать представление о предмете, достаточное для понимания 2-й и 3-й части. Там они почти всегда обходятся счётными множествами и используют конструктивный подход (за исключением обсуждения моделей и всяких там лёвенгеймов и скулемов).
Конечно же, их доказательство этой теоремы не настоящее. Они доказывают её через "и т.д.", и не приводят перед доказательством ни определения бесконечного множества, ни списка аксиом, на которые можно опираться. А существует ведь много разных определений бесконечного множества, доказательство эквивалентности которых требует аксиомы выбора. С некоторыми определениями и без аксиомы выбора эта теорема может и не выполняться: https://en.wikipedia.org/wiki/Axiom_of_choice#Statements_consistent_with_the_negation_of_AC). С другой стороны, одно из определений просто говорит, что "бесконечное множество — это множество, которое содержит счётное подмножество", и тут уже дажё аксиома выбора не нужна. 🙂
С аксиомой выбора можно просто вполне упорядочить бесконечное множество и отрезать от него начальный кусок длины ω.
Наверное, можно и их доказательство привести в нормальный вид, сохранив основную идею, но заменив "и т.д." на использование аксиомы выбора.
Re: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
(тоже на rsdn) написал про ошибку в доказательстве Тьюринга о неразрешимости проблемы остановки. GC>Но что-то тот форум какой-то вялый. GC>Может кто-то здесь прокомментирует?
О, господи. Ну сведением же решается, тот же семестр вуза, где вычислимость проходят.
Пусть ваш алгоритм с 0 и 1 на выходе существует. Берем его и строим другой: когда ваш алгоритм завершается с ответом о расходимости входного, запускаем бесконечный цикл. Получаем алгоритм, про который Тьюринг доказал, что его не существует
Re: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Здравствуйте, 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)
Если четный — то самый первый анализатор (в стеке вызовов) зависнет, соответственно и вся цепочка зависнет.
То есть, если мы хотели получить неопределенное поведение такого анализатора, то мы его получили. Не более того.
И никаких выводов о существовании или несуществовании алгоритмов сделать нельзя.
Здравствуйте, ·, Вы писали:
GC>> "Странное" тут в том, что Тьюринг допускает анализатор, который зависает сам. GC>> И не рассматривает остальные варианты. ·>Это не допущение, а просто такое понятие, которое позволяет выразить в формальном виде проблему остановки.
Вот тут интересно. Спасибо. Надо будет ознакомится с этим поподробнее.
Оказывается, тут какое-то формальное определение есть, спасибо.
GC>> Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается GC>> и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа. ·>Да пожалуйста. Но теперь тебе придётся выразить проблему остановки для такого варианта анализатора.
Интересно, многого я не знал. Но выразить проблему это же не такая большая проблема?
Выразить проблему — это же задача порядка проще?
Третий Рим должен пасть!
Re: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Кажется, если доказательство Тьюринга — это не доказательство,
то Матиясевич доказал что-то очень близкое, или даже тоже самое.
Он доказал что нельзя создать универсального способа решения Диофантовых уравений,
а это десятая проблема Гильберта.
А эти проблемы (проблема останова, диофантовых уравнений) очень близки.
Возможно, что доказательство, которое завершил Матиясевич и есть настоящее доказательство неразрешимости проблемы останова машины Тьюринга.
Третий Рим должен пасть!
Re: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Здравствуйте, GhostCoders, Вы писали:
GC>·>Это не допущение, а просто такое понятие, которое позволяет выразить в формальном виде проблему остановки. GC>Вот тут интересно. Спасибо. Надо будет ознакомится с этим поподробнее. GC>Оказывается, тут какое-то формальное определение есть, спасибо.
Не совсем прям уж определение, это просто часть док-ва. Т.е. понятие такого анализатора вводится не просто так, а чтобы на его основе построить доказательство теоремы.
GC>>> Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается GC>>> и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа. GC>·>Да пожалуйста. Но теперь тебе придётся выразить проблему остановки для такого варианта анализатора. GC>Интересно, многого я не знал. Но выразить проблему это же не такая большая проблема? GC>Выразить проблему — это же задача порядка проще?
Ну да, это будет гипотезой. Интереснее эту гипотезу доказать.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[5]: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Здравствуйте, GhostCoders, Вы писали:
GC> ·>Не совсем прям уж определение, это просто часть док-ва. Т.е. понятие такого анализатора вводится не просто так, а чтобы на его основе построить доказательство теоремы. GC> Опять не понимаю. Вводится понятие противоречивого анализатора, затем показывается, GC> что этот противоречиввый анализатор противоречив.
Ключевое по той ссылке "Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?"
Т.е. сама проблема остановки равносильна конкретно этому анализатору, который сформулирован определённым образом.
А если ты вводишь какие-то другие термины, какие-то другие виды анализаторов, которые делают что-то не то или не так, то скорее всего они не будут равносильны проблеме и смысл затеи теряется.
Я во всё не вникал, но вот тут очевидная ошибка.
GC> Почему? Возьмем алгоритм сортировки. GC> Построим "другой" алгоритм сортировки, который будет вызывать нормальный алгоритм сортировки и зависать. GC> Тьюринг доказал, что его не существует. Отсюда вывод, что алгоритмов сортировки не существует.
Нет, Тьюринг доказал несуществование не любых зависающих алгоритмов, а конкретно Анализатора.
Алгоритм сортировки с зависанием — очевидно существует. Более того, тривиально построить алгоритм, который берёт на вход любой алгоритм и преобразует его в зависающий.
Здравствуйте, nikov, Вы писали:
N>Доказательство теоремы Матиясевича (или, как он её называет сам, MRDP-теоремы) показывает, каким образом вопрос об остановке любого алгоритма можно механически переформулировать как вопрос наличия решений у некоторого диофантова уравнения. Если бы мы могли алгоритмически определять наличие решений у любого диофантова уравнения, то мы могли бы использовать этот способ, чтобы алгоритмически решать вопрос об остановке любого алгоритма. А это, как показал Тьюринг, невозможно. Следовательно, заключил Матиясевич, не существует алгоритма, который бы определял наличие решений у любого диофантова уравнения.
Интересно. То есть Матиясевич ссылается на доказательство Тьюринга при доказательстве невозможности решений диафантовых уравнений в общем виде?
А то я тут недавно предположил, что если мы найдем способ алгоритмически решать проблему останова, то мы сможем решать любые диафантовы уравнения или доказывать,
что они не имеют решений
Поэтому решить задачу останова МТ с бесконечной лентой — увы, либо невозможная задача, либо чрезвычайно сложная.
Получается, что задача останова МТ есть более общий случай решения всех диофантовых уравнений,
включая и доказетельство теоремы Ферма и возможное доказательство abc-гипотезы.
Третий Рим должен пасть!
Re[4]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, ·, Вы писали:
·>Т.е. он не всегда зависает, а тогда и только тогда твой "нормальный" анализатор возвращает ноль.
Скопирую свой ответ из другой темы.
Да, уже нашел на английской википедии, функция g().
И получается, что типа Анализатор (is_halt) в таком случае становится "предсказателем" результата работы этой функции g().
(в смысле не возвращаемого значения, а результата зависнет-не зависнет).
И функция g() имеет все способы чтобы "нагадить" Анализатору, сделав все в точности наоборот, вместо зависания, что-нибудь вернуть,
или вместо успешного завершения зависнуть.
Типа человеку предсказали умереть через год, а он заключил пари с предстказателем, так вот этот человек, чтобы выиграть пари, специально прожил до ста лет.
Или наоборот. Предсказатель предсказал, что человек будет жить до 100 лет, а человек, заключил с ним пари, что предсказатель не прав,
и совершил самоубийство на следующий день, чтобы выиграть пари.
Хотя у меня останутся возражения, что, мол, Анализатор возвратил результат функции (зависла или нет)
для того гипотетического запуска (или запуска через интерпретацию) этой функции, который он сделал (или мог гипотетически сделать) сам,
а не того запуска, что запустил его самого.
То есть Тьюринг считает, что алгоритм должен работать строго детерминированно — как в функции в функциональных языках программирования,
а не императивных, с наличием глобальных переменных, и когда результат функции зависит от предыдыщих (разные всякие undefined behaviour)
вызовов. Проще говоря, Тьюринг не допускает дребезга результатов алгоритмов (типа как undefined behaviour).
P.S. Вспомнил про "предсказания", я до этого дошел раньше, когда интересовался темой.
Поэтому и меня тогда и интерес пропал. А сейчас, склероз, опять забыл...
Третий Рим должен пасть!
Re[5]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, 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 это не свойство алгоритма, это относится к семантике ЯП, об его спецификации. Т.е. когда человек глядит на код и видит некую конструкцию, но не может сказать как сработает всё окружение начиная от компиляторов, их версий, линковщиков, железа, таймингов и т.п. о том что именно произойдёт.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
GhostCoders:
GC>Другой (мой) вариант существования анализатора, это случай, когда анализатор всегда останавливается GC>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа.
GC>Это же просто и естественно (особенно для программистов), иметь анализатор, GC>который возвратит 1 или 0, типа функции is_halt(), которая принимает на вход некую программу. GC>Если переданная программа может потенциально зависнуть, то сам анализатор должен быть валиден и всегда останавливаться, GC>возращая 1 или 0.
Как ты определишь, что программа зависла? Может быть просто долго считает?
Читал про такое неформальное доказательство проблемы останова: анализ программы может в той или иной степени абстракции потребовать ее выполнения.
(абстрактное выполнение это выполнение упрощенной программы. Напр. подстановка sign(a)*sign(b) вместо sign(a*b), другие подобные преобразования.)
То есть против конкретного метода анализа останова всегда может быть найден контрпример.
Модератор-националист Kerk преследует оппонентов по политическим мотивам.
Re[3]: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
·:
GC>>>анализатор всегда останавливается GC>>>и возвращает 1 или 0 в зависимости от того, зависла или нет анализируемая программа. LK>>Если анализатор остановится, как ты возобновишь работу анализируемой программы? ·>Это какое-то заблуждение и вообще не в тему. Зачем анализатору запускать программу? На то он и Анализатор. Он может просто, например, искать бесконечные циклы.
Против любого такого анализатора можно придумать хитрый цикл, который анализатор не находит.
Цикл может зависеть от довольно широкого контекста состояний программы (переменных). Для анализа состояний и понадобится выполнение.
Модератор-националист Kerk преследует оппонентов по политическим мотивам.
Re[2]: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Здравствуйте, nikov, Вы писали:
N>Конечно, это связано. .... По сути, эти два результата эквивалентны.
Спасибо! Сейчас бегло прочитал это, интуитивно понял, но не в деталях.
В данный момент я не обладаю детальными знаниями о теоремах Геделя, поэтому надо будет подтянуть.
P.S.: Я так понимаю, что вы профессионально этим занимаетесь? Статические анализаторы какие-то строите?
Третий Рим должен пасть!
Re[2]: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Здравствуйте, Bill Baklushi, Вы писали:
BB>Как ты определишь, что программа зависла? Может быть просто долго считает?
Я вот тут сделал кое-какие предположения
Это, конечно, в большинстве своем, наверное, предположения дилетанта,
часть из которых, наверное, известны, а часть неверна.
Если интересно, ознакомтесь. Возникнут какие-то уточняюшее вопросы или замечания — пишите — я отвечу по мере своих возможностей.
Кратце, Машина Тьюринга (теоритический компьютр) может зависнуть циклически и ациклически.
Зависнуть циклически — войти в одно из своих предыдущих состояний.
Зависнуть ациклически — "уйти в бесконечность".
Реальные компьютеры могут зависать толко циклически (если нет потока информации из вне).
Третий Рим должен пасть!
Re[6]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, ·, Вы писали:
GC>>Типа человеку предсказали умереть через год, а он заключил пари с предстказателем, так вот этот человек, чтобы выиграть пари, специально прожил до ста лет. GC>>Или наоборот. Предсказатель предсказал, что человек будет жить до 100 лет, а человек, заключил с ним пари, что предсказатель не прав, GC>>и совершил самоубийство на следующий день, чтобы выиграть пари. ·>Ничего не понял. Что за g()? Каким ещё предсказателем?
На самом деле довольно просто.
Вместо русской вики я открыл английскую и сразу понял фокус.
def g():
if halts(g):
loop_forever()
Допустим анализатор (функция halts) решил, что функция g() зависнет.
То эта самая функция g(), назло анализатору (для того, чтобы ему "нагадить" и дискредитировать его) нагло возвращает какое-то значение.
То есть делает "предсказание" анализатора неверным.
И наоборот, если анализатора для g вернет что она не зависнет, то она зависает.
Но думаю, вы это и сами знали?
GC>>Хотя у меня останутся возражения, что, мол, Анализатор возвратил результат функции (зависла или нет) GC>>для того гипотетического запуска (или запуска через интерпретацию) этой функции, который он сделал (или мог гипотетически сделать) сам, GC>>а не того запуска, что запустил его самого. ·>В док-ве теоремы никто ничего запускать не должен и вообще такое понятие не используется. Анализатор не обязан говорить "зависла ли". Он может сказать "зависнет ли". Т.е. условоно говоря... анализатор может быть статическим — смотреть на код и определять его зависаемость без запуска этого кода на выполнение.
Да, все верно. Только может быть статическим, а может и интерпретировать программу, например.
При интерпретации программы сохранять список посещенных полных состояний МТ и проверять на каждом шагу,
что новое состояние не находится в этом списке. Если находится — то мы определили, что анализуруемый алгоритм
завис циклически за конечное число шагов. Ациклические зависания таким способом не определить.
Если интересно — почитайте тут
мои рассуждения дилетанта, может и найдете для себя что-нибудь новое и интересное.
И да, тут же описан случай "The halting problem is theoretically decidable for linear bounded automata (LBAs)",
который я и называю "зависнуть циклически".
GC>>— как в функции в функциональных языках программирования, а не императивных, с наличием глобальных переменных, и когда результат функции зависит от предыдыщих (разные всякие undefined behaviour) GC>>вызовов. Проще говоря, Тьюринг не допускает дребезга результатов алгоритмов (типа как undefined behaviour). ·>У тебя всё смешалось в кучу. Теорема об алгоритмах. А ЯП это лишь способ записи алгоритмов. Undefined behaviour это не свойство алгоритма, это относится к семантике ЯП, об его спецификации. Т.е. когда человек глядит на код и видит некую конструкцию, но не может сказать как сработает всё окружение начиная от компиляторов, их версий, линковщиков, железа, таймингов и т.п. о том что именно произойдёт.
Вот тут я с вами согласен. Смешалось, да.
Третий Рим должен пасть!
Re[5]: Ошибка в доказательстве Тьюринга о неразрешимости проблемы о
Здравствуйте, ·, Вы писали:
·>А с чего ты это взял? Мамой клянёшься? Собственно Тьюринг это и сделал — он формально доказал теоретическую невозможность построения такого умного анализатора,
Вы оба доказываете друг другу одно и тоже — то что Анализатор нельза построить, ошибочно предполагая, что собеседник придерживается противоположного мнения.
Третий Рим должен пасть!
Re[7]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, GhostCoders, Вы писали:
GC>·>Ничего не понял. Что за g()? Каким ещё предсказателем? GC>На самом деле довольно просто. GC>Вместо русской вики я открыл английскую и сразу понял фокус. GC>
GC>def g():
GC> if halts(g):
GC> loop_forever()
GC>
GC>Допустим анализатор (функция halts) решил, что функция g() зависнет.
Анализатор на вход берёт собственно сам текст этого самого g().
GC>То эта самая функция g(), назло анализатору (для того, чтобы ему "нагадить" и дискредитировать его) нагло возвращает какое-то значение.
Функция уже определена в виде этого кода. Покажи где в этом коде оператор нагаживания, я что-то не вижу.
GC>То есть делает "предсказание" анализатора неверным. GC>И наоборот, если анализатора для g вернет что она не зависнет, то она зависает. GC>Но думаю, вы это и сами знали?
У тебя какие-то хитрые алгоритмы, обладающие сознанием, волей и желанием нагадить. С такими алгоритмами да, теоремы доказывать не получится, их только уговаривать можно, Кнутом и Страуструпом.
GC>Да, все верно. Только может быть статическим, а может и интерпретировать программу, например. GC>При интерпретации программы сохранять список посещенных полных состояний МТ и проверять на каждом шагу, GC>что новое состояние не находится в этом списке. Если находится — то мы определили, что анализуруемый алгоритм
И что с этим можно сделать полезного?
GC>завис циклически за конечное число шагов. Ациклические зависания таким способом не определить.
И как мы отличим ациклический алгоритм от циклического? Ну сделали мы TREE(3) шагов — цикла не нашлось. Что это значит? Да ничего. Т.е. и циклические алгоритмы таким способом тоже не определить. Можно определить лишь алгоритмы работающие не дольше некоего N кол-ва шагов. Собственно всё. Для этого можно просто счётчик операций запустить и не выпендриваться с запоминанием состояний.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, ·, Вы писали:
·>Функция уже определена в виде этого кода. Покажи где в этом коде оператор нагаживания, я что-то не вижу.
В википедии все есть.
·>У тебя какие-то хитрые алгоритмы, обладающие сознанием, волей и желанием нагадить.
Не алгоритмы, а программисты и математики, которые такие алгоримы пишут
·> С такими алгоритмами да, теоремы доказывать не получится, их только уговаривать можно, Кнутом и Страуструпом.
Ну вообще-то я уже признал, что я ошибался, и в доказательстве Тьюринга нет ошибки, еще пару постов выше.
А этот пост, с которым ты споришь, я привел как объяснение свой собственной неправоты.
Тут вообще нет предмета спора.
·>И что с этим можно сделать полезного?
Просто показал, что какие-то методы нахождения зависаний все такие есть.
GC>>завис циклически за конечное число шагов. Ациклические зависания таким способом не определить. ·>И как мы отличим ациклический алгоритм от циклического? Ну сделали мы TREE(3) шагов — цикла не нашлось. Что это значит? Да ничего.
Пока никак.
Третий Рим должен пасть!
Re[9]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, GhostCoders, Вы писали:
GC>·>Функция уже определена в виде этого кода. Покажи где в этом коде оператор нагаживания, я что-то не вижу. GC>В википедии все есть.
Видимо, я не понимаю что ты имеешь в виду, в вики вроде ничего такого нет.
GC>·>У тебя какие-то хитрые алгоритмы, обладающие сознанием, волей и желанием нагадить. GC>Не алгоритмы, а программисты и математики, которые такие алгоримы пишут
Но теорема-то об алгоритмах, а не о математиках. Не понимаю к чему ты это всё говоришь.
GC>·>И что с этим можно сделать полезного? GC>Просто показал, что какие-то методы нахождения зависаний все такие есть.
Это какой-то бессмысленный метод. Можно просто ограничивать алгоритм по памяти и/или времени. И собственно всё.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[10]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, ·, Вы писали:
·>Здравствуйте, GhostCoders, Вы писали:
GC>>·>Функция уже определена в виде этого кода. Покажи где в этом коде оператор нагаживания, я что-то не вижу. GC>>В википедии все есть. ·>Видимо, я не понимаю что ты имеешь в виду, в вики вроде ничего такого нет.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do. No f can exist that handles this case.
Выделил жирным. "Специально сделать обратно" — это очень вольно можно интерпретировать как "нагадить" .
GC>>·>У тебя какие-то хитрые алгоритмы, обладающие сознанием, волей и желанием нагадить. GC>>Не алгоритмы, а программисты и математики, которые такие алгоримы пишут ·>Но теорема-то об алгоритмах, а не о математиках. Не понимаю к чему ты это всё говоришь.
Забудь, просто неудачная шутка.
GC>>·>И что с этим можно сделать полезного? GC>>Просто показал, что какие-то методы нахождения зависаний все такие есть. ·>Это какой-то бессмысленный метод. Можно просто ограничивать алгоритм по памяти и/или времени. И собственно всё.
Может быть и так. С другой стороны этот метод позволяет находить зависания в очень хитрых циклах (вложенных в друг друга,
или в переплетении спагетти goto) в случае циклического зависания и относительно небольшого периода цикла зависания.
Третий Рим должен пасть!
Re[11]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, GhostCoders, Вы писали:
GC> specifically do the opposite of what f predicts g will do. No f can exist that handles this case. GC> Выделил жирным. "Специально сделать обратно" — это очень вольно можно интерпретировать как "нагадить" .
Если оператор логического отрицания считать нагаживанием... ок теперь понятно откуда столько говнокода
GC> ·>Это какой-то бессмысленный метод. Можно просто ограничивать алгоритм по памяти и/или времени. И собственно всё. GC> Может быть и так. С другой стороны этот метод позволяет находить зависания в очень хитрых циклах (вложенных в друг друга, GC> или в переплетении спагетти goto) в случае циклического зависания и относительно небольшого периода цикла зависания.
Достаточно чтобы в цикле был какой-нибудь long++ счётчик (а это практически наверняка в каком-нибудь не совсем уж тривиальном коде) то Солнце скорее прогорит, чем ты дождёшься когда состояние повторится. Правда память под состояния у тебя закончится гораздо раньше. Т.е. работать такой подход на практике может только в очень специфических сценариях.
N>Очень советую почитать на эту тему:
N> N>Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов, выложены авторами в свободный доступ: https://www.mccme.ru/free-books, ftp://ftp.mccme.ru/users/shen/logic N>• Часть 1. Начала теории множеств N>• Часть 2. Языки и исчисления N>• Часть 3. Вычислимые функции N> N>Все они излагают материал очень подробно
Но не всегда верно, а именно, в Началах теории множеств приводится широко распространённое неверное доказательство теоремы о том, что в каждом бесконечном множестве содержится счётное подмножество.
Re[13]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>·>Правда память под состояния у тебя закончится гораздо раньше. EP>Это же классика — алгоритм черепахи и зайца. Достаточно хранить только два состояния. EP>Запускаем две машинки: медленную и быструю. Если есть цикл — то быстрая врежется состоянием в состояние медленной.
Хорошая оптимизация, но не ничем поможет в контексте обсуждения. Этот алгоритм предназначен чтобы находить _длину_ цикла в списке про который заведомо известно, что в нём конечное число элементов. Этот алгоритм неприменим если мы этого не знаем.
Если это применить для обсуждаемой задачи, то это будет эквивалентно тупому счётчику шагов.
Да, по пространству машина работать сможет. Но с точки зрения практики это всё равно не поможет, т.к. с т.з. времени мы всё равно не сможем обнаруживать циклы, т.к. нужно конечное число шагов. Грубо говоря, если мы сделали N шагов, но цикл так и не обнаружили — мы всё ещё не знаем есть ли цикл или нет. А если просто выполнить машинку до N-го шага, то это будет быстрее и эффективнее чем запускать две машинки.
По-моему, из этого можно даже сделать вывод, что интерпретирующие Анализаторы сложнее тупого счётчика бессмысленны.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[14]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, ·, Вы писали: ·>Хорошая оптимизация, но не ничем поможет в контексте обсуждения. Этот алгоритм предназначен чтобы находить _длину_ цикла в списке про который заведомо известно, что в нём конечное число элементов. Этот алгоритм неприменим если мы этого не знаем.
Этот алгоритм применим к любым машинам с ограниченной памятью. Он не работает на МТ ровно потому, что её память ничем не ограничена: мы запросто можем получить неостановимый алгоритм без циклов.
Физические машины имеют ограниченную память, так что рано или поздно алгоритм либо остановится, либо войдёт в состояние, которое уже было.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[15]: Ошибка в доказательстве Тьюринга о неразрешимости про
Здравствуйте, Sinclair, Вы писали:
S>·>Хорошая оптимизация, но не ничем поможет в контексте обсуждения. Этот алгоритм предназначен чтобы находить _длину_ цикла в списке про который заведомо известно, что в нём конечное число элементов. Этот алгоритм неприменим если мы этого не знаем. S>Этот алгоритм применим к любым машинам с ограниченной памятью. Он не работает на МТ ровно потому, что её память ничем не ограничена: мы запросто можем получить неостановимый алгоритм без циклов. S>Физические машины имеют ограниченную память, так что рано или поздно алгоритм либо остановится, либо войдёт в состояние, которое уже было.
Ты подменяешь рассмотрение алгоритма конкретной его физической реализацией, это ошибка.
Теоретически, конечно, да. Любая физическая машина это конечный автомат, меньше по мощности чем МТ. Там не только объём памяти ограничен, но и количество шагов, которые машина способна выполнить, хотя бы из-за ограниченности доступного кол-ва энергии. Так что тут сомнений нет — любой алгоритм на любой физической машине завершается рано или поздно. Но это не делает сам алгоритм конечным и нисколечко не помогает обойти проблему неразрешимости.
К тому же, практически, если прикинуть количество состояний хотя бы для одного жалкого килобайтика памяти, то становится всё очень печально и использовать МТ для моделирования физических машин оказывается более адекватным.
Так что физические машины имеют практически бесконечную ленту как в МТ.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Против любого такого анализатора можно придумать хитрый цикл, который анализатор не находит.
