Доказательство окончено.

Замечание. В доказательстве последней теоремы использован прием, который состоит в сведении одной задачи разрешимости к другой, более общей, задаче разрешимости.

При этом, если существует метод решения второй задачи, то он может быть преобразован в метод решения и первой задачи.

В таком случае будем говорить, что первая задача сводится ко второй задаче, поскольку из существования алгоритма решения второй задачи следует существование алгоритма решения первой задачи.

Следовательно, задача распознавания эквивалентности частично-рекурсивных функций оказалась более общей задачей по сравнению с задачей распознавания всюду определенности частично-рекурсивных функций.

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

Говорят также о том, что множество R₂ сводится к множеству R₃.

Упражнение.

1. Обозначим как R - множество {(n,m,k)| f_n(m) = k}.

Доказать, что R - неразрешимое множество, сведением его к неразрешимому множеству R₁;

2. Доказать неразрешимость множества частично-рекурсивных функций одной переменной, которые определены для почти всех значений начальных данных;

3. Доказать неразрешимость множества частично рекурсивных функций одной переменной, принимающих лишь два значения 0 и 1.