Здравствуйте, 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