Вычислимость частично рекурсивных функций по Тьюрингу - часть 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)

$\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), заданную с помощью оператора минимизации.

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