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

Но. Все таки эта проблема остановки не дает мне покоя.
Постараюсь выразить свои сомнения и мысли понятно.

Получается, формально Тьюринг доказал, что такой Анализатор для МТ (Машины Тьюринга) построить нельзя.
По одной, довольно простой причине.
Есть такая "паталогическая" функция g(), на которой Анализатор всегда будет выдавить неверные результаты:

def g():
    if halts(g):
        loop_forever()

Причем здесь Анализатор представлен в удобной и естественной форме — как функция halts(),
которая возвращает 1 если анализируемая программа остановится и 0 если анализируемая программа зависнет.

У этой функции g() есть возможность вызвать Анализатор для самой себя.
Если Анализатор скажет, что функция g() остановится (вернет 1) то в функции g() после вызова Анализатора мы намеренно зависаем,
делая результат анализа Анализатором функции g() неверным. И наоборот.

Как минимум существует 1 реализация такой функции, на которой, независимо от устройства самого Анализатора,
он будет давать неверные результаты.

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

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

А какой практический толк в анализе таких патологических программ?
Понятно, что практического смысла в этом мало.
Если бы мы могли построить Анализатор, который бы умел анализировать лишь те программы,
которые не являются "паталогическими" и не вызывают Анализатор, то это было дало нам какие-то плоды на практике.
Например, мы могли бы анализировать алгоритмы сортировки, алгоритмы поиска кратчайшего пути, и прочие алгоритмы,
которые представлят практическую ценность.

Что будет если мы изначально ограничем область применения Анализатора?
Скажем, например, что на "патологических" программах результат Анализатора не определен.

Это как с опрерацией деления. Делить на ноль нельзя. Однако мы же пользуемся операцией деления.
Не объявили же о том, раз на некотором подмножестсве входных аргументов операция является невалидной,
то и операции деления не существует?

Возможно ли что в новой форме Анализатор существует?

Я вот сейчас интуитивно предполагаю, что множество "патологических" программ будет нечетким, крайне расплывчатым.
То есть задача определить вот это множество "патологических" программ не будет тривиальной,
скорее даже всего неразрешимой.
Например, патологическую функцию g() можно записать чуть-чуть по другому, обфусцировать как-то.
Еще можно сам вызов Анализатора "заинлайнить" в самом коде функции g().
Причем разных версий ограниченных Анализаторов, которых может быть бесконечное множество, и еще обфусцировать их.

Это раз. Второе, это что нам скажет Гёдель? Не будет ли это протироречить с теоремой о неполноте Гёделя?
Или такой Анализатор как раз и будет "неполным"?

Скажем, можно ли все таки построить такой ограниченный Анализатор для диофантовых уравнений?
В таком случае, мы должны доказать, что программы решения диофантовых уравнений не являются паталогическими.

В конце-концов Великую Теорему Фермы все-таки доказали. Соответственно, доказали то,
что какой-то класс сложных алгоритмов для Машины Тьюринга,
соответствующий этому уравнению (a^n + b^n = c^n) никогда не останавливается.

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

GC>Тут важно отметить, что Тьюринг под Анализатором считает строго формально, такой алгоритм,
GC>который имеет анализировать все программы, включая и так называемые "патологические".
GC>Если бы мы могли построить Анализатор, который бы умел анализировать лишь те программы,
GC>которые не являются "паталогическими" и не вызывают Анализатор, то это было дало нам какие-то плоды на практике.

Не совсем понятно, какие программы считать "патологическими". Ну например, у нас есть полезная "непатологическия" программа: интерпретатор какого-нибудь языка программирования. Если интепретатор может исполнять любые программы, то ему можно передать "патологический" код, и его поведение станет "патологическим". Или же полезная система компьютерной алгебры, которая умеет решать некоторые диофантовы уравнения. Ей можно передать такое уравнение, что её поведение также станет "патологическим". Ясно, что рамки этого понятия довольно размыты.

Разумеется, есть полезные — назовём их так — "частичные" анализаторы, которые умеют правильно говорить "да", "нет", или зависать (или же говорить "не знаю"). Например, многие инструменты для статического анализа могут обнаруживать бесконечные циклы или бесконечную рекурсию, причём не только в тривиальном виде `while (true) { … }`, но и с условиями для выхода из цикла, которые по какой-то далеко не очевидной причине никогда не могут оказаться верными. Не говоря уже о более примитивных частичных анализаторах, как тот, что просто запускает программу, и отвечает "не знаю", если её выполнение не прекратилость после выполнения N шагов.

Очень интересное — на мой взгляд — последствие теоремы Тьюринга, это то, что его доказательство даёт явный алгоритмический способ трансформировать любой частичный анализатор A в другой, более мощный A′, который не только успешно справляется со всеми случаями, которые мог распознать A, но и в добавок может дать определённый ответ ("да"/"нет") для некоторых случаев, в которых A отвечал "не знаю". Эту процедуру можно повторить несколько раз. Более того, можно написать цикл, который последовательно конструирует A′, A″, A‴, …, и запускает их параллельно в надежде, что какой-то их них в конце концов решит поставленную задачу. Само собой, этот анализатор — назовём его B — по-прежнему будет частичным, хотя и гораздо более мощным, чем изначальный вариант A. Но ничто не мешает нам создать B′, B″, B‴, …, C, C′, …, D, D′, …, затем обернуть это в цикл и получить AA, затем BB, … и так далее. Мы ограничены лишь тем, насколько большие рекурсивные ординалы мы способны придумать и правильно реализовать в коде.

https://en.wikipedia.org/wiki/Recursive_ordinal

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

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

Правда в том, что функция Анализатора действительно является рекурсивной функцией. Но на счет вывода о тотальной нерешаемости... Моя практика пока что не подтверждает этот результат. Решаемость заканчивается там, где заканчивается обозримость. А обозримость пропадает только там где: a) не реализована соотв. функциональность Анализатора б) программа не является обозримой.

Пункт А очевиден. Пункт Б может исходить только из криптографической необозримости.

Но тем не менее, на данный момент человечество считает что так называемая необозримая обфускация в общем виде недостижима.

Поэтому я бы ставил вопрос так: либо доказательство Тьюринга о проблеме останова неверно либо необозримая обфускация в общем виде невозможна.

Как видите, на сегодняшний момент это патовая ситация: как бы две обшепринятые теории являются доказанными, но в то же время они противоречат друг другу.

GC>А какой практический толк в анализе таких патологических программ?
GC>Понятно, что практического смысла в этом мало.

В этом очень много смысла! Оптимизаторы компиляторов строятся на этом аппарате, и чем более Анализатор "всевидящий", тем более выдающиеся результаты появляются на выходе компилятора.

Если перевести это на язык бизнеса, то грубо это выглядит примерно так:

1. Берем среднего или даже слабого кодера
2. На выходе компилятора появляется программа с такими параметрами производительности, которые смог бы достичь только очень высококлассный специалист
3. Разницу в полученных и потраченных деньгах капиталист ложит себе в карман

Теперь масштабируйте это на несколько миллиардов населения планеты. Совсем ведь не малый практический смысл!