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