После прочтения Сипсеровской «Теории вычислений» машины Тьюринга вошли в голову на столько глубоко, что я не могу воспринимать термины из теории вычислимых функций без перевода их на язык МТ. Вот цитата из «Вычислимых функций» Верещагина и Шеня: «Пусть U — произвольная главная универсальная функция. Тогда множество тех n, при которых функция U n является нигде не определенной, неразрешимо.» Кто бы мог подумать, что это означает «Проблема проверки того, что машина Тьюринга повисает на любых входных... read more
