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

      § 3. Теорема о совпадении классов частично-рекурсивных
                и вычислимых по Тьюрингу функций

     Частично-рекурсивная функция может быть не всюду определенной,
а каждая примитивно-рекурсивная функция всюду определена. Поэтому
класс примитивно-рекурсивных функций строго содержится в классе час-
тично-рекурсивных и даже общерекурсивных.
     Теорема. Функция вычислима по Тьюрингу тогда и только тогда, ко-
гда она частично рекурсивна.
     Определение. Множество называется рекурсивно перечислимым, если
оно совпадает с множеством значений некоторой общерекурсивной функции.
     Примером могут служить множества четных и нечетных чисел.
     Замечание. Каждое рекурсивное перечислимое множество порожда-
ется некоторой машиной Тьюринга, которая вычисляет соответствующую
общерекурсивную функцию.
     Рассмотрим характеристическую функцию множества M :
                                      �0, если x � M ,
                           � M ( x) � �
                                      �1, если x � M .
     Замечание. Числовое множество M называется рекурсивным, если
общерекурсивна характеристическая функция этого множества.
     Замечание. Каждое рекурсивное множество является рекурсивно-
перечислимым.
     Доказательство. Очевидно, что если множество M рекурсивно, то
существует машина Тьюринга T1 , которая вычисляет его характеристиче-
скую функцию. Построим новую машину T2 , которая сначала изготавливает
два экземпляра исходного слова и помнит фиксированный элемент из M .
Затем она работает как машина T1 , но сохраняет один экземпляр исходного
слова, т. е. слова на ленте в начальной конфигурации. Если в результате
работы T1 получается единица, машина T2 стирает на ленте все кроме со-
                                    31