Замечание. В доказательстве последней теоремы использован прием, который состоит в сведении одной задачи разрешимости к другой, более общей, задаче разрешимости.
При этом, если существует метод решения второй задачи, то он может быть преобразован в метод решения и первой задачи.
В таком случае будем говорить, что первая задача сводится ко второй задаче, поскольку из существования алгоритма решения второй задачи следует существование алгоритма решения первой задачи.
Следовательно, задача распознавания эквивалентности частично-рекурсивных функций оказалась более общей задачей по сравнению с задачей распознавания всюду определенности частично-рекурсивных функций.
Из приведенного доказательства следует, что разрешимость проблемы эквивалентности влечет разрешимость проблемы всюду определенности, т.е. проблема всюду определенности программ сводится к проблеме их эквивалентности.
Говорят также о том, что множество R2 сводится к множеству R3.
Упражнение.
1. Обозначим как R - множество {(n,m,k)| fn(m) = k}.
Доказать, что R - неразрешимое множество, сведением его к неразрешимому множеству R1;
2. Доказать неразрешимость множества частично-рекурсивных функций одной переменной, которые определены для почти всех значений начальных данных;
3. Доказать неразрешимость множества частично рекурсивных функций одной переменной, принимающих лишь два значения 0 и 1.
