программу вида 0:

где t,i означает одну из операций х2, хЗ, Х5,: 30. Все эти операции перерабатывают числа вида 2°35 в числа того же вида. Поэтому, начиная перерабатывать число 2* по программе (2), мы после к-то шага вычислений получим (см. и. 14.3) пару вида (2"•3•5 i), где 2•З-5"= - полученное в этот момент число, а г - номер приказа в программе (2), который следует далее выполнять над числом 2•3-5=.

С парой (2° • 3-5", i) сопоставляем конфигурацию (а, Ь, с; i) трехленточной машины Минского, име1ош;ей внутренние состояния до, д, . . ., д. Нам остается подобрать программу (1) машины М так, чтобы выполнялось условие: если алгоритм А переводит пару (2-3-5 i) в пару (2"-3"»5, /), то машина М должна переходить из конфигурации (а, Ь, с; i) в конфигурацию (и, v, w, j).

Эта цель, очевидно, будет достигнута, если мы поступим следующим образом:

а) Если t,i = : 30, то вносим в программу М команды

qtOOO qaJiTyTy, qtabc -> q.TJJ, (abс ф 0).

б) Если 1,1- х2, то в программу М вносим команды

даЬс -> g.T-iToT, (а, Ь, с = О, 1).

в) Если ti - хЗ, то вносим команды

qtabc- да.ТоТ-уТ,.

г) Еслп t,i = X 5, то вносим кодшнды

qiabc -> q.ToToT-y.

Так как алгоритм А перерабатывает пару (2*, 1) в пару (2W, 0), то машпна М с командами а) - г) из конфигурации {х, О, 0; 1) переходит в конфигурацию (/ {х), О, 0; 0), что и требовалось.

Рассмотрим теперь более детально двухленточные машины Мпнского. Пусть qo, q-y, . . ., g,, - внутрепнпе состояния какой-нибудь двухленточноп машины Минского М. Тогда для полного задания машины М достаточно

Рис. 4

задать ее программу, состоящую из команд вида qiab длТТу,

удовлетворяющих условию (2).

Далеко не все частично рекурсивные функции вычислимы на двухленточных машинах Минского в указанном выше смысле. Напри.мер, не существует двухленточной машины Минского, перерабатывающей х ъ х (см. Б а р -3 д и и ь [1]). Тем не менее, если значения аргумента и функции кодировать степенями двойки, то вычислимость частично рекурсивных функций восстанавливается.

Теорема 2 (Минский [1]). Для каждой частично рекурсивной функции f{x) существует двухленточ-ная машина Минского, которая для любого натурального X перерабатывает число 2 в число 2/<=), если / {х) определено, и работает безостановочно, не переходя в заключительное внутреннее состояние qo, если / {х) не определено.

Для краткости условимся тройкой (а, Ь, д,) обозначать ту конфигурацию машины Минского, при которой д - внутреннее состояние машины, & а, b - расстояния от воспринимаемых машиной ячеек до левых концов первой и соответственно второй лент. Например, (О, 2; д;) есть конфигурация, определенная машинными словами gjl, lOgjO и изображенная на рис. 4. Формулой (а, Ь; qi) \- (с, d; qj) будем обозначать утверждение, что машина, начав работать в конфигурации (а, Ь; qi), через конечное число тактов работы приобретет конфигурацию (с, d; q). Если машина из конфигурации (а, Ь; qi) неносредственно переходит в конфигурацию (с, d; qj), то пишем

(а, Ь; qi) (с, d; qj). (3)

Как уже говорилось, задать машину Мпнского - это значит указать ее программу. Однако вместо того, чтобы указывать команды, составляющие программу машины, мы будем писать преобразования (3), выио.лняемые машиной. При этом следует иметь в впду такие обстоятельства. Пусть, например, указывается, что машпна выполняет

вычисляет функцию g {x) и пусть для некоторой магиини Минского М с внутренними состояниями до, д, . . ., gs, gib • •, 4si = 1, 2, . . .) имеем

(z, 0; g;) !- Hi (z), 0; gaj), если t,i (z) определено, (7) (z, 0; qi) - (z, 0; gg.), если (z) не определено. (8)

Тогда машина М вычисгяет ту же функцию g {х), что и алгоритм А.

В самом деле, пусть, начиная с заданного чпсла х, алгоритм А после т шагов дает чпсло х,п и указание выполнять приказ с номером i. Покажем, что в этом слчае

(х, 0; gi) 1- {.г,п, 0; г)-

Для т = о это утверждение тривиально. Пусть оно верно для какого-нибудь т. Если t,i {Хт) определено, то алгоритм А после {т -j- 1)-го шага дает число (Хт) и указание выполнять приказ с номером а. Но в этом случае

(х,п, 0; qi) h ili im), 0; дщ)

и потому

(х, 0; gi) [- Zi (хт), 0; qa{).

Аналогично доказывается это соотношение и в случае, когда li (Хт) не определено.

Пусть теперь алгоритм А перерабатывает число х в число у. Это значит, что через какое-то число шагов т алгоритм А дает число у и указание выполнять приказ с номером 0. По доказанному

{х, 0; gi) Ь {у, 0; до),

т. е. машина М перерабатывает х ъ у.

Если, начиная с х, алгоритм А работает вечно, то получаем бесконечную последовательность

{х, 0; gi) 1- («1, 0; g;,)

показывающую, что машина М в этом случае также работает вечно.

Перейдем к доказательству основной теоремы. Пусть / (х) - заданная частично рекурсивная функция. Согласно теореме 2 из и. 14.3 существует операторный алгоритм А, перерабатывающий 2 в 2/(=), программа которого имеет вид (6), где i-й приказ есть или

(с = 2, 3, 5),

:с а

(с = 30).

(10)

Пусть Л/ - машпна Минского с внутреннплш состоя-нпямп до, gi, . . ., g„, каждое нз которых соответствует определенному приказу программы (6), и донолните.чьными состояниями qij (i = 1, . . .; j = О, 1, . . .), точное чпсо которых будет указано ниже. Нам надо найтп такую программу для машины Л1, чтобы былп выполнены условия (7), (8) леммы 1. Рассмотрим какое-нибудь i, 1 i s.

преобразование

(2, 5;д,)~>(1, 6;д,.). (4)

Отсюда следует, что машина выполняет команду

qtOO -> qjTiT i

И потому для любых положительных а, b

{а, Ь; дг) -> (а - 1, 6 + 1; q). (5)

В то же время наличие в программе машины преобразования (4) еш;е ничего не говорит о том, во что перейдут конфигурация (О, Ь; gi) или конфигурации (6, 0; д,), (О, 0; д,), где 6 > 0. Поэтому, присоединив к программе машины преобразование (4), мы не можем присоединять к программе преобразования, противоречашие преобразованиям (5), но все еш;е можем по произволу присоединить преобразования

(О, Ь; qi) (и, у; д) {и = О, i; v = Ь, b ± 1), {b, 0; qi) -> К, Vx, gp) {Vi = 0, i;ui = b, b ± 1), (0, 0; g;) -> («2, щ; qv) (Щ, Щ = 0, 1).

Нам надо для каждой частично рекурсивной функции / (х) указать программу машины Минского, перерабатывающей 2 в 2W. Нижеследующая лемма сводит эту задачу к двум простым частным случаям.

Лемма!. Пусть операторный алгоритм А с программой

Пусть i-ш приказ в программе (6) имеет вид (9). Постараемся написать такую серию команд для машины М, содер-жаш;их лишь внутренние состояния qi, qi, . . ., go Ча, в результате которой условие (7) для этого i будет выполнено. Пусть а > 0. Вносим в программу машины ikf следующую серию преобразований:

(а, 0; qi) -> {а, 1; д)

-> {а, 2; qtz) ->...-> (а, с; qt) (а - 1, с; qt) (И)

и дополняем ее еще преобразованием

{а, 1; qt) {а, 2; q,). (12)

Тогда, если в серии (11) а - 1 О, то в силу команд, отвечающих преобразованиям (И), (12), конфигурация (а - 1, с; qi) далее будет меняться следующим образом:

(а - 1, с; дО (а - I, с -Ь 1; qd) . . .

. . (а - 1, 2с; ?;,) (а - 2, 2с; дО ->

(а - 2, 2с -I- 1; д) ->...-> (О, ас; qt).

Чтобы переставить числа О и ас, дополняем программу преобразованиями

(О, ас; qi) (1, ас - 1; q,) -» (2, ас - 2; q,) . .

. . . {ас, 0; дго) («с, 0; ?„). (13)

В результате условий (И) - (13) для машины М будет гарантировано свойство

(а, 0; qt) \- {са, 0; д„) (а > 0). (14)

Чтобы гарантировать свойство (14) и для а = О, внесем в программу М преобразование

(О, 0; qt) (О, 0; q).

(15)

Итак, внося в программу машины М команды (И) - (13), (15) для тех г, для которых г-й приказ программы А имеет вид (9), мы обеспечим для этих значений i выполнение условпя (7) из летш 1.

Теперь рассмотрим более сложный слчай, когда i-й приказ имеет вид (10). Прежде всего в программу машины М вносим команды, отвечающие для ж > с, г/ > О следующей серии преобразований:

{х, у; qi) (ж - 1, у + 1; qi) (ж - 2, г/ + 1; д)

(а; - с, г/ + 1; д,)- {х - с, у + i; qi), (16)

И команды, отвечающие преобразованиям (13) и (14). Вследствие команд (16) для ж > с, г/ О имеем

{х, у; qd h- {х-с,у + \.; qi)

И, значит,

{х, 0; qi) I- (О, а; : с; gO, если X делится на с. Так как из (16), (13), (14) вытекает (О, X : с; qi) \- {х:с, 0; д),

{х, 0; qi) - {х: с, 0; д»), если х : с определено.

Пусть теперь а; не делится на с, ж = cz -j- г, О < г < с. В силу (16)

. {х, 0; qt) Н {г, z; qi) \- {О, z + 1; qi,).

Нам надо теперь от конфигурации (О, z -Ь 1; qir) перейти к конфигурации {х, 0; gg). Поэтому к программе М добавляем преобразования (z = 1, 2, . . .; г =1, . . ., с - 1)

(О, Z -Ь 1; qir) (1, z; girl) . . . (с, z; gi.) ->

(с -Ы, z - 1; gi,i), (17)

в силу которых

(О, г -Ь 1; qir) - (cz + 1, 0; gi,i). Наконец, добавляя в программу преобразования

(cz + 1, 0; gi,i) -> (cz + 2, 0; qi) -> . . .

. . . -> (cz + r, 0; qi„) {cz + r, 0; gp), (18)

ползучим

{x, 0; qi) [- {x, 0; gg), если ж : с не определено.

Мы видим, что машина Минского с нрогратюй, построенной согласно правилам (И) - (13), (15) - (18), удовлетворяет условиям лелшы 1, что и требовалось.

Так же, как и для одноленточных машин Тьюринга (и. 12.5), для машин Минского естественно формулируются следующие две проблемы.

1) Проблема остановки. Задана машина Минского М {своей програмлюй). Указать алгоритль, рас-познающийте конфигурации {а, Ъ; q), начиная с которых машина останавливается через конечное число тактов работы.