Математическая логика и теория алгоритмов. Стенюшкина В.А. - 64 стр.

       Задача называется алгоритмически неразрешимой, если не существует
машины Тьюринга (или рекурсивной функции, или нормального алгоритма
Маркова), который её решает.
       Неразрешимой является «проблема остановки»: по описанию алгоритма
A и аргументу x выяснить, остановится ли алгоритм, если исходные данные – x.
Как следствие этой неразрешимости – невозможность создания общего для лю-
бой программы алгоритма отладки программ. Неразрешимой является также
проблема распознавания эквивалентности алгоритмов: нельзя построить алго-
ритм, который по любым двум алгоритмам (программам) выяснял бы, вычис-
ляют они одну функцию или нет. Имеет место следующая теорема.
       Теорема Райса Никакое нетривиальное свойство вычислимых функций не
является разрешимым.
       Смысл этой теоремы: какое бы свойство вычислимых функций ни взять
(периодичность, ограниченность, равенство другой, наперёд заданной функции
и т. д.), нельзя построить общий алгоритм, например, машину Тьюринга, кото-
рый по произвольному алгоритму A определял бы, обладает вычисляемая им
функция fA этим свойством или нет.
       Приведём ещё пример невычислимой функции. Пусть выбрано некоторое
уточнение алгоритма. Тогда все алгоритмы, предназначенные для вычисления
числовых функций, можно закодировать натуральными числами, Пусть Ai обо-
значает алгоритм с номером i, а ϕi - функцию, вычисляемую алгоритмом Ai.
Требуется построить алгоритм, вычисляющий функцию f(n) = ϕn(n)+1, если ал-
горитм применим к числу n, и f(n)=0 в противном случае. Эта проблема нераз-
решима. Действительно, если такой алгоритм Ak существует, то должно быть
f(k)=ϕk(k) и f(k)=ϕk(k)+1, что невозможно.