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

C>chukichuki wrote:

>> Как вы думаете, решение такой задачи возможно ?

C>Невозможно теоретически. Данная проблема легко сводится к "проблеме
C>останова" для машины Тьюринга, которая доказано неразрешима:
C>1. Предположим, что первый алгоритм вызывает останов МТ.
C>2. Тогда второй алгоритм для эквивалентности, как минимум, тоже должен
C>вызывать останов МТ.
C>3. Определить вызывает ли данный алгоритм останов МТ в общем случае —
C>невозможно.

Доказательство совершенно некорректно. Из того, что в обоих случаях невозможно определить останов само по себе не следует, что невозможно доказать эквивалентность алгоритмов, работающих за конечное время. Чтобы убедиться в некорректности твоего "доказательства", достаточно ограничить множество алгоритмов, эквивалентность которых предполагается доказывать, таким образом, чтобы они завершались за конечное время (что, кстати, вполне разумно ). И сопоставить с твоими выкладками, начав со слова "предположим".