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



             

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


 \mathcal{N}_2
копирует свой вход с разделителем #, т.е. по любому входу w выдает w # w.

Через E обозначим м.Т., которая ничего не делает.

Пусть

 \mathcal{N}_3 = \mathbf{par}_{\#}(E, M_g),
т.е. вход вида
|^{x_1}*\ldots*|^{x_n}* |^y\# |^{x_1}*\ldots*|^{x_n}* |^y
машина
 \mathcal{N}_3
перерабатывает, используя
 \mathcal{M}_g,

в

|^{x_1}*\ldots*|^{x_n}* |^y\# |^z
, где z= g(x1,… ,xn, y)

? на входе вида w # v проверяет непустоту v (т.е. условие v > 0).

\Phi( w\#v)=\left \{ \aligned 0,\qquad \textit{если }v \neq \wedge\\ 1\qquad \textit{если }v= \wedge \endaligned \right .

Таким образом, при v=g(x1,…,xn,y) машина ? проверяет условие g(x1,…,xn,y)

0.

 \mathcal{N}_4
по входу вида
|^{x_1}*\ldots*|^{x_n}* |^y\# w
стирает #w и прибавляет к y единицу, т.е. выдает результат:
|^{x_1}*\ldots*|^{x_n}* |^{y+1}.

Наконец,

 \mathcal{N}_5
по входу
|^{x_1}*\ldots*|^{x_n}* |^y\# w
выдает |y, стирая ненужные блоки символов.

Ясно, что каждая из перечисленных м.Т.

 \mathcal{N}_1,
 \mathcal{N}_2
,
 \mathcal{N}_3
,
 \mathcal{N}_4
,
 \mathcal{N}_5
и ? легко реализуема. Построим теперь с их помощью следующую м.Т.
 \mathcal{M}_f:

 \mathcal{M}_f: \\ \mathcal{N}_1; \mathcal{N}_2; \mathcal{N}_3; \\ {\bf while\ } \Phi\ {\bf do\ } \mathcal{N}_4;\ \mathcal{N}_2;\ \mathcal{N}_3\ {\bf enddo};\\ \mathcal{N}_5.

Из этого определения непосредственно следует, что

 \mathcal{M}_f
вычисляет функцию fn(x1,…, xn), заданную с помощью оператора минимизации.




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