так что щО) есть машинное слово, описываюш;ее состояние машины, которое она приобретает через i тактов работы, отправляясь от начального состояния ш. Утверждения m(i) = Ь и = Ь, i > 1, будем записывать соответственно в виде от b и от [- Ь.

Изложим теперь точнее закон построения машинного слова OTi) но заданному машинному слову от. Из описания в г) работы механического устройства следует, что машина может выполнять несколько действий. Если машина, имея внутреннее состояние и воспринимая ячейку ленты в состоянии aj, переводит внутреннюю память в состояние qs и одновременно состояние aj воспринимаемой ячейки заменяет состоянием а, то говорят, что машина: выполняет команду

qaj -> (ja,. (2):

Если при указанных условиях машина переводит внут- реннюю память в состояние q и передвигает управляю-ш;ую головку в соседнюю справа или слева ячейку ленты, то говорят, что машина выполняет команду

qtaj-qR или соответственно команду

где R, L - особые символы.

Совокупность всех команд, которые может выполнять машина, называется ее программой. Так как работа машины по условию целиком определяется состоянием в данный момент ее внутренней памяти qt и состоянием воспринимаемой ячейки aj, то для каждых д,, aj[{i = 1, . . . . . ., п; j = О, i, . . ., т) программа машины должна содержать одну и только одну команду, начинаюш;уюся словом дау. Таким образом, программа машины с символами {flo, «1, . . ., От} и состояниями {до, qi, . . ., g„} содержит в точности 7г {т -f 1) команд. Мы будем иредиолагать, что для каждого набора команд вида (2)-(4), содержаш;его

для каждой пары д,, (i = 1....., ге; / = О, 1, . . ., m)

точно одну команду вида qiUj а, существует машина Тьюринга с этой программой.

Рассмотрим пример. Пусть внешний алфавит машины состоит из символов О, 1, внутренний - из символов до, 91) (721 где до - символ остановки, О - символ пустой

ячейки. Пусть программа машины состоит из команд

qfi-gR, gaOJ-gol, qiqR, qi ~> qR. (5)

Посмотрим, как будут меняться состояния этой машины при тех или иных ее начальных состояниях. Вспоминая смысл команд (2)-(4), непосредственно находим

gill Igil llgiO llOgO llOgol, gglOl IgOl Igoll.

Ясно, что таким же образом и в общем случае, имея программу машины ф и какое-нибудь машинное слово от, можно строить любое число слов цепочки от 1= от(1) от(2)

представляющих последовательные состояния машины.

В дальнейшем нас совсем не будут интересовать фактическое устройство машины Тьюринга, ее ленты, управляющей головки. Мы будем интересоваться лишь структурой последовательностей машинных слов, описывающих последовательные состояния, принимаемые машиной Тьюринга. С математической точки зрения машина Тьюринга - это просто определенный алгоритм для переработки машинных слов. Так как способ переработки машинных слов известен, если известна программа машины, то будем считать машину Тьюринга заданной, если заданы ее внешний и внутренний алфавиты, программа и указано, какие из символов обозначают пустую ячейку и заключительное состояние.

Процесс построения слова т но заданному машинному слову от выше был описан в таких терминах, как «передвинуть управляющую головку», «изменить состоя-нне ячейки» и т. п. Мы теперь хотим дать иное описание этого процесса, опирающееся лишь на понятие подстановки слова с в слово а вместо первого вхождения слова Ь в й. Операция подстановки была введена в п. 11.2 и ее результат был обозначен через Sb (й; Ь; с).

Пусть Ь, с - слова в алфавите, не содержащем chaibo-ла -В данном разделе формулой b -> с будем обозначать «командз»: в заданное слово вместо первого вхождения слова Ь подставить слово с,- а сами формулы Ь -> с будем называть подстановочными командами. Ес.лп какое-нибудь слово й содержит подслово Ь, то резу.льтатом выпслнения команды b -> с над словом й будет слово Sb (й; Б; с). Если же b не входит в й, то команду b с

иногда называют неприменимой к слову а и результат ее применения считают неопределенным в отличие от всегда определенной операции Sb.

Посмотрим теперь, какими подстановками из машинного слова т можно получить машинное слово т-\ Так как иногда слово т преобразуется в слово т при помо-ш;и пристройки ячейки, то нам надо уметь отличать крайние буквы машинных слов. Для этого введем новые символы и, у, не входяш;ие во внутренний и внешний алфавиты рассматриваемой машины Тьюринга £. Если m - какое-нибудь машинное слово, то слово ити будем называть расширенным машинным словом, описывающим то же общее состояние машины £, что и слово т. Мы хотим сформулировать закон получения слова um> v из слова umv.

Пусть программа машины £ содержит команду д„а; -» -> gpffl;- и заданное расширенное машинное слово содер-лшт подслово qaUi. Ясно, что в этом случае слово umf-b получается из слова umv подстановкой qaOi~>q,aj; ее и будем считать соответствующей команде д„а, -> qaj.

Если машинное слово от содериит подслово qaO-t, а соответствующая машинная команда имеет вид дг -> -> gpL, то легко убедиться, что для получения из слова uxnv слова ихФЪ надо над словом иш выполнить ту подстановку из совокупности

diqadi -> qaai.

uqaUi -> uqaai,

которая применима к слову umv. В частностп, последняя подстановка применима только тогда, когда д - самая левая буква в т, т. е. когда надо пристраивать ячейку слева.

Аналогично, есчп машинное слово m содержит подслово qadi, а соответствующая машинная команда имеет вид дай; -qf,R, ТО чтобы ПЗ слова umv получить слово um<г, достаточпо над словом umv выполнить ту пз подстановочных команд

qaUiaa aq о, qaaiUx ад., i,

qadiV amaov.

которая применима к слову umv. Так как слово да,а входит лишь один раз в слово т, то к слову umv применима лишь одна из команд (6), (7) и потому порядки следования команд в (6) и (7) безразличны, важны лишь их совокупности.

I Сформулируем теперь правило получения слова mW измашинного слова от в общем виде. Пусть задана машина Тьюринга своими алфавитами {ао, ai, . . ., а), {до, qi, . . q-n), выделенными символами ао, до и совокупностью машинных команд Для каждой машинной команды из строим но указанным выше правилам соответствующие подстановочные команды, совокупность которых назовем совокупностью подстановочных команд машины ф. Пусть эта совокупность состоит из команд

«1 Ьь U2->Ьг,..., вг Ь,. • (8)

Согласно изло}кенному для того чтобы из расширенного машинного слова umv получить слово итЪ, описывающее непосредственно следующее состояние машины Тьюринга, достаточно над словом umv выполнить ту из подстановочных команд (8), которая применима к слову umv.

Если ни одна из команд (8) не применима к слову umv, то ш содержит заключительный символ до и потому слово umv описывает заключительное состояние машины.

12.2. Вычислимые функции. Рассмотрим произвольную машину Тьюринга £ с внешним алфавитом {ао, а, . . ., Urr, внутренним алфавитом {до, qi, . . ., gn} и программой sp. Программа sp позволяет преобразовывать определенным способом одни машинные слова в другие. Однако вычисгения при помощи машины % мы будем производить не над машинными словами, а над словами в редуцированном алфавите *) {а, . . ., о} машины Z. В связи с этим введем еще несколько определений.

Пусть m - какое-нибудь машинное слово в алфавите машпны £. Через т* условпмся обозначать слово, получающееся из m вычеркиванием символа д и всех вхождений символа Со. Говорят, что слово а, записанное вреду-цпрованном алфавите, перерабатывается машиной £ в слово Ь, символически sp (й) = Ь, если для некоторого натурального i

go t (дхйой), Ь = (дхаой)*. (1)

Стгаолы ао, и, v исключаются.

Если же никакое i не удовлетворяет условию до 6 (giaou)<*>,

то говорят, что машина неприменима к слову а или что результат переработки слова а машиной £ неопределенный. В этом случае говорят также, что выражение ф (й) имеет неопределенное значение.

В машинных терминах это означает следуюш;ее. Пусть • • • 4 - какое-нибудь слово (возможно и пустое) в редуцированном алфавите . . ., а}. Берем ленту, состояш;ую из s + 1 ячейки. Левую ячейку оставляет пустой, а в остальные последовательно «вписываем» символы aj,, . . ., aj. Помеш;аем ленту в машину (рис. 2) так, чтобы машина воспринимала самую левую (пустую) ячейку. Приводим внутреннюю память машины в начальное состояние Qi и пускаем машину в ход. В силу своего устройства машина £ начнет последовательно принимать состояния

{giaoUj... а) \= {qiaoaj.. . a/D \= (дюоЯу. .. а,)(У \= . ..

Теперь возможны два случая: либо в какой-то момент времени i внутренняя память машины придет в заключительное состояние и, значит, машинное слово, оиисываюп];ее состояние машины в этот момент, будет иметь вид ujgob;, либо внутренняя память никогда не придет в состояние qo. В первом случае ф (яу, . . . uj) == ajt, а во втором случае 95 {а; ... а.) имеет «неопределенное» значение.

Пусть F (х) - какая-нибудь словарная частичная функция в редуцированном алфавите {а, . . ., а} машины £. Если для каждого слова х в этом алфавите

i(f)=(r),

то говорят, что машина £ вычисляет функцию F (г).

Рассмотрим, например, машину с программой (5) из предыдуш,его раздела. Редуцированный алфавит этой машины содержит .лишь симвсл 1 и потому слова в этом алфавите 1шеют вид

Л, I, И, 111, . . .

Из Соотношений

дО ОдзО i= Ogol, gll . . . 1 Igl . . . 1 . . . t= 1 . . . IgiO

\z \ . . . lOgOt 1 . .. . lOgol

видим, что sp (f) = fl.

С другой стороны, рассмотрим машину £j с алфавитами {О, 1}, {до, gJ и ирогралшой

giO -> gii?, gil -qR. Из соотношений

gO OgiO OOgiO . . ., g,01 . . . 1 . . . 01 . . . IgiO 01 . . . lOgO . . .

заключаем, что £i вычисляет нигде не определенную функцию.

Возвраш;аясь к машине Тьюринга с произвольными алфавитами {ао, а, . . ., а,„}, {до, gi, . . ., g„} и программой sp, условимся говорить, что машина £ перерабатывает s-ny слов fx, . . ., fs, записанных в редуцированном алфавите {«1, . . ., Ят}, в слово г, если для подходяш;его натурального i

qo 6 (giaofiaof2 • • • аоГ,)(), f = (giaofi. .. aoxj"*.

В этом случае пишут ф (fi, . . ., fs) = f- Если для любого i

qo 6(9iaof1• • aoSsY\

TO говорят, что машина £ неприменима к s-ке (fi, . . ., fs) и что выражение (fi, . . ., fs) имеет неопределенное значение.

Говорят, что словарная частичная функция F (fi, . . . . . ., fs), определенная в алфавите {а, . . ., а-}, состав-ляюш;ем часть редуцированного алфавита {а, . . ., а-, . . . . . ., Ото} машины £, вычисляется машиной £, если для любой s-кп слов fx, . . ., fs в алфавите {а, . . ., а}

i(fi,..., Ы = 51)(Р1,---, Ь)-

Таким образом, с каждой машиной Тьюринга £, имею-ш,ей указанный внешний алфавит {ао, о, . . ., о}, сопоставляются частичные словарные функцип ф (f), Ф (fi, Рг), • • •, определенные в редуцированном алфавите • •", а}. Остальные функции, вычислимые на маши-