Но, как всегда, есть нюансы.
Если интересно прошу под кат.
Введение
В 1936 году Алан Тьюринг доказал, что нет общего алгоритма, анализирующего другие алгоритмы и указывающий, будет зависать программа или нет.
Хотелось бы сразу расставить все точки над ё и описать термины которые используются мной чтобы не было не понимания.
Зависание программы – алгоритм будет работать БЕСКОНЕЧНОЕ количество времени вне зависимости от скорости выполнения команд, и параллельных вычислений. Какой бы большой суперкомпьютер мы бы не построили, алгоритм всегда будет выполняться бесконечное количество времени.
Выполнение программы за конечное время – алгоритм на любой машине закончит свои вычисления какими бы объемными они не были. Например если алгоритм выполняется 300 миллионов лет это не значит, что он завис, просто на текущих ресурсах ему надо выполняться 300 миллионов лет и он ВСЕГДА завершится.
Теперь можно продолжать.
Доказательство Тьюринга можно описать так: есть некий оракул S (алгоритм) на вход которого подаётся описание алгоритма N и входные данные X. Программа останавливается и возвращает 1, если алгоритм N не останавливается, получив на вход X.
Программа не останавливается в противном случае, если алгоритм N останавливается, получив на вход X. Если же мы скормим нашему оракулу описание самого себя, то будет противоречие и алгоритм будет противоречить сам себе. Подробно можно посмотреть на вики.
Оракул существует, но ему нужен брат
Вас не смущает тот факт, что оракул должен зависнуть если алгоритм, который он анализирует останавливается, меня вот прям сильно сей факт смущает, поэтому для доказательства немного подкорректируем вывод оракула. Пусть оракул возвращает 1 либо 0. Ну что с того, спросите вы, ничего не поменялось, если мы на псевдокоде напишем:
If (оракул(N)==0){ While (true){ } } То противоречие останется, но если мы добавим брата оракула, то всё становится интересней:
Пусть у нас есть два оракула, входные параметры одинаковы у обоих оракулов, но выводы различаются:
S1 возвращает 0 или 1 но что значат эти 0 или 1 неизвестно, об этом знает только второй оракул.
S2 возвращает 0 или 1 для обозначения данных первого оракула, но не даёт информации о работе алгоритма. 1 означает что у первого оракула 1 будет означать бесконечное выполнение алгоритма, 0 остановка. А вот ноль на оборот у первого оракула 0 будет означать бесконечное выполнение алгоритма, 1 остановка.
Оракулы ВСЕГДА выполняют анализ за конечное время, но с оговоркой. Описание оговорки будет чуть ниже.
Два оракула нужны для того, чтобы алгоритм получив данные от одного оракула не смог узнать о своём будущем, до полного выполнения всей программы. Так как узнав результат своей работы, алгоритм может изменить своё поведение, тем самым опровергнув утверждение оракула.
Оракулы запускаются на двух параллельных машинах Тьюринга, синхронизированных такт в такт. Оракулы соединены очень быстрой связью, настолько быстрой что решения они принимают одновременно.
Теперь как это будет выглядеть на псевдокоде:
Запрос к первому оракулу
If (оракул(N)==0){ While(true){ } }Запрос к второму оракулу
If (оракул(N)==0){ While(true){ } }Оба оракула вернут ноль что будет означать что алгоритм зависнет.
В конце выполненных алгоритмов мы можем взять и соотнести данные тем самым получив ответ.
Но есть еще один нюанс, все входные данные должны быть конечными. Ресурсы машины, также должны быть конечными. Если хоть что-то будет бесконечным, то гарантировать анализ оракулами за конечное время нельзя.
Заключение
Так как Алан Тьюринг доказал, что общего алгоритма быть не может, значит с большой долей вероятности в нашей теории кроется ошибка. Поэтому всех неравнодушных прошу в комментарии помочь найти такую ситуацию, которая бы смогла помочь решить текущую задачку.
Источник
