Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 32 стр.

храняемого экземпляра исходного слова и останавливается. Если же в ре-
зультате работы машины T1 получается нуль, T2 стирает все буквы на лен-
те, пишет фиксированный элемент из M и останавливается.
      Обратное включение неверно, т. е. существует рекурсивно перечис-
лимое, но не рекурсивное множество.
      Следовательно, для рекурсивного перечислимого, но не рекурсивно-
го множества нельзя решить, принадлежит ли ему данный элемент или нет.
      Вышесказанное может быть использовано при доказательстве несу-
ществования алгоритма для решения всех задач данного класса.
      Замечание. Не всякое числовое множество является рекурсивно-
перечислимым.


           § 4. Задачи и упражнения для самостоятельного решения

      1. Доказать, что данные функции примитивно-рекурсивные:
f(x, y) = x(y+1); f(x) = 2x.
      2. Построить машину Тьюринга, вычисляющую функции:
f(x, y) = x+y; f(x) = 2x.




                                  32