Мысли о проблеме останова
От: GhostCoders Россия  
Дата: 09.03.20 20:12
Оценка: 5 (1)
Итак, мы по итогам предыдущей темы, выснили что доказательство Тьюринга верно, а ошибался как раз я.
Я приношу свои извинения и можно на этом было бы поставить точку.

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

Получается, формально Тьюринг доказал, что такой Анализатор для МТ (Машины Тьюринга) построить нельзя.
По одной, довольно простой причине.
Есть такая "паталогическая" функция 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) никогда не останавливается.
Третий Рим должен пасть!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.