Введение в схемы, автоматы и алгоритмы



             

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


Теорема 10.1. Для всякой ч.р.ф. f существует м.Т.

\mathcal{ M}_f,
вычисляющая функцию f.

Доказательство. Доказательство проведем индукцией по определению частично рекурсивной функции f.

Базис. Вычислимость простейших функций машинами Тьюринга очевидна.

Индукционный шаг. Покажем, что операторы суперпозиции, примитивной рекурсии и минимизации сохраняют вычислимость по Тьюрингу. Все используемые м.Т. будем предполагать односторонними со стандартными заключительными конфигурациями.

Суперпозиция. Пусть Fm и fn1,…, fnm

- ч.р.ф., вычислимые на м.Т.

 \mathcal {M}_F, \mathcal { M}_{f_1}, \ldots, \mathcal {M}_{f_n},
соответственно. Пусть функция Gn получена из них с помощью суперпозиции: Gn=[Fm;fn1,…, fnm]. Тогда м.Т.
 \mathcal { M}_G,

вычисляющая G, работает следующим образом:

  1. m раз копирует вход
    |^{x_1}*\ldots *|^{x_n},
    отделяя одну копию от другой символом #;
  2. на полученном слове вида
    |^{x_1}*\ldots *|^{x_n}\# \ldots \# |^{x_1}*\ldots *|^{x_n}
  3. запускает параллельную композицию машин
     \mathcal { M}_{f_1}, \ldots, \mathcal {M}_{f_n}
    и получает конфигурацию вида
    |^{ y_1}\# \ldots \# |^{y_n},
    где yi=fi(x1,…,xn) (i
    [1,m]).
  4. заменяет все символы 0023 на *;
  5. затем запускает программу м.Т.
     \mathcal {M}_F
    на получившемся после этапа 3) входе вида
    |^{ y_1}* \ldots * |^{y_n},
    и вычисляет требуемое значение
    G(x_1,\ldots,x_n)=F(y_1, \ldots, y_m).

Если обозначить м.Т., выполняющую копирование на этапе (1), через Копm, а м.Т., выполняющую замену # на * на этапе (3), через Зам*#, то требуемую для суперпозиции м.Т.

\mathcal { M}_G
можно представить как

\textit{Коп}^m; \mathbf{par}_{\#}( \mathcal { M}_{f_1}, \ldots , \mathcal {M}_{f_n}); \textit{Зам}_*^\#; \mathcal {M}_F

Примитивная рекурсия. Пусть функция Fn+1(x1,… ,xn,y) получена с помощью оператора примитивной рекурсии из функций gn(x1,…, xn) и fn+2(x1,… ,xn, y, z), которые вычислимы на м.Т.

\mathcal{ M}_g
и
\mathcal {M}_f
. Определим вспомогательные м.Т.:

  • \mathcal{M}_1,
    используя
    \mathcal{ M}_g,
    строит по входу вида
    |^{x_1}*\ldots *|^{x_n}*|^y
    конфигурацию на ленте
    |^y*|^{x_1}*\ldots*|^{x_n}*\wedge*|^{g(x_1,\ldots,x_n)};
  •  \mathcal{ M}_2,
    используя
     \mathcal{M}_f,
    строит по входу вида
    |^y*|^{x_1}*\ldots*|^{x_n}*|^u*|^z
    конфигурацию
    |^y*|^{x_1}*\ldots*|^{x_n}*|^{u+1}*|^{f(x_1,\ldots,x_n,u,z)};
  •  \mathcal{M}_3
    на входе вида
    |^y*|^{x_1}*\ldots*|^{x_n}*|^u*|^z
    выдает в качестве результата
    |^z;
  • ? на входе вида
    |^y*|^{x_1}*\ldots*|^{x_n}*|^u*|^z
    проверяет условие y
    u.

Построение каждой из указанных м.Т. достаточно очевидно. Из них можно получить, используя определенные в предыдущем разделе конструкции "языка программирования" для машин Тьюринга, требуемую м.Т.

\mathcal {M}_F:

 \mathcal {M}_1\/;\ \mathbf{ while\ }\Phi\ \mathbf{ do\ } \mathcal{ M}_2\ \mathbf{enddo};\ \mathcal {M}_3

Минимизация. Пусть fn(x1,…, xn) = ? y [ gn+1(x1,…, xn,y)=0] и м.Т.

 \mathcal{M}_g
вычисляет функцию gn+1. Определим следующие вспомогательные м.Т.:

 \mathcal {N}_1
приписывает аргумент 0 ко входу, т.е. вход вида
|^{ x_1}*\ldots *|^{x_n}
переводит в конфигурацию на ленте
|^{x_1}*\ldots*|^{x_n}*\wedge
(напомним, что при унарном кодировании 0 соответствует пустой символ).




Содержание    Вперед