Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 40
Текст из файла (страница 40)
е. определена схемой Т(х, О) я(х); 1 (х, р + 1) й (х, у, ! (х„ у)), где функции я и й вычислимы машинами Т» и Т, соответ. ственио, работающими с правой полулентой. Построим машину Ть вычисляющую !. Машина Т~ должна воспроизводить процесс вычисления по схеме примитивной рекурсии, т. е, последовательно вычислять !'(х, О) д(х); ((х, 1) = =й(х, О, !(х, О)); ..., !(х,(+1) Ь(х,(,!(х,1))... до тех пор, пока не вычислит Й(х, у, !(х, у)).
Этот процесс, начинающийся с конфигурации д~!»«1», разбивается на блоки, выполняющие следующие действия (для каждого блока указана заключительная конфигурация, служащая начальной для следующего блока; состояния не конкретизированы, а символ д указывает положение головки): 1. Подготовить данные для вычисления д(х): О! ° 1»О Од!».- 2.
Вычислить д(х) на правой полуленте: О! ° 1»О 91м»~. 3. Проверить (с восстановлением), верно ли, что у=0. Если да, то блок 7. Если нет, то блок 4. 4. Подготовить данные для вычисления Ь(х, 1, ! (х, !)) и записать 1 в крайнюю слева пустую ячейку (т. е. прибавить 1 к числу слева от исходнык данных, выделенных маркерами О): 1~+' О !» . !» О<~!» «1~ «1м о 5, Вычислить и на правой полуленте 1гм О1' ° 1УО Ч1ых ~ л» О). 6, Проверить, верно ли, что у=!+1. Если да, то блок 7. Если нет, то блок 4. 7. Выдать результат (стереть все слева от д, вернуться обратно и остановиться), Блок 2 реализуется машиной Тз, блок 5 — машиной Т,.
Построение блоков 1, 3, 6, 7 очевидно. Блок 4 сдвигает число 1"<'' 'н»' '»=!п'о, полученное на предыдущем шаге блоком 5, на х+1+2 ячейки вправо и записывает в освободившийся пробел слово 1 ° 1'. (число 1' равно числу, записанному в начале работы блока 4 слева от исходных данных). Похожий процесс осуществлялся с помощью машины Т„„при построении универсальной машины Т, поэтому на деталях останавливаться не будем.
13" 195 Таким образом, машина Ть реализующая оператор примитивной рекурсии для и=1, построена. Для и) 1 все остается таким же, увеличивается лишь число переменных и соответственно маркеров в векторах исходных данных 1, а и Ь. Реализация трех рекурсивных операторов позволяет по рекурсивному описанию любой частично-рекурсивной функции (представлению ее в виде конечной последовательности применений операторов о„', )г и (г к простейшим функциям) построить реализующую ее машину Тьюринга.
П Теорема бЛ. Всякая функция, вычислимая на машине Тьюринга, частично-рекурсивна. Прежде чем доказывать.эту теорему, несколько слов в пояснение. На первый взгляд — особенно после рассуждений о том, что алгоритмы могут иметь дело с иечисловыми объентами, н примеров машин Тьюринга, выполняющих нечисловые операции (сдвиг, запись, переписывание и т.д.),— таное утверждение может покззаться слишком слабым для того, чтобы говорить об эквивалентности рекурсивных функций, имеющих дело с числами, и машин Тьюринга, которые могут не только вычислять.
Однако от любых объектов можно перейти к числовым с помощью кодирования, причем это кодирование оказывается крайне простым. Дело в том, что с точни зрения машины, не внладывающей в обозреваемые ею символы никакого «смысла», а лишь выполняющей с ними предписанные операции, нет особой разинцы между числамн и «нечислами». Свои элементарные действия: чтение, запись, сдвиг, смену состояния — машина может выполнять при наличии на ленте кая цифр, так и других символов.
Разш<ца существует лишь для пас при интерпретации полученных результатов. В частности, ничто ие мешает интерпретировать любой алфавит ленты А=(аь...,а ) кан множество цифр иьичной системы счисления, а слово, записанное на леитц — как ш-ивисе число. Тогда любав деятельность машины Тьюринга рассматривается как преобразование чисел, т.
е, как вычисление числовой функции. Именно такая интерпретация и подразумевается в теореме 5.7; доназательство теоремы заключается в том, чтобы точно описать эту интерпретацию (называемую арифметизацией) и показать, что лю. бое преобразование, реализуемое машиной Тьюринга, если его интерпре. тировать как вычисление, является частично-ренурсивным. Переходим к доказательству теоремы 5.7. Сначала опишем арифметизацию машин Тьюринга. Как уже указывалось, символы на ленте интерпретируются как т-ичные цифры (например, в порядке их перечисления в алфавите, т.е. а~ кодируется цифрой (). При этом символу Х всегда ставится в соответствие О.
Поскольку непустых символов 196 на ленте в любой момент — конечное число, то соглашение позволяет иметь дело только с конечными числами. Для определенности (и простоты обозначений) при иллюстрациях будем считать, что А=(1, л), а вместо Х будем писать О. Состоянию д; машины поставим в соответствие число 1; буквой г обозначим код заключительного состояния; сдвиги закодируем так: Я=1, Ь=О (как было показано в $5.2, случай с Е можно не рассматривать), Символы ленты, состояния и сдвиги не будем отличать от их кодов.
Система команд машины Т с множеством состояний Я и алфавитом А превращается при таком кодировании в тройку числовых функций Ч~„:ЯХА-«Я (функция следующего состояния), ~р,:ЯХА-«А (функция печатаемого символа), ~рз:ЯХА — «(О, 1) (функция сдвига). Если Х, содержит команДУ йчаз — г(,а;г(и, то сР~(дь а;) =г(б сР,(срь ау) =а~,. <~з(аь а;) =Нм Отметим, что все эти функции заданы на конечном множестве ЯХА и, следовательно, примитивнорекурсивны. Каждой конфигурации ад;аА1 однозначно ставится в соответствие четверка чисел (а, дь ая р), определяемых следующим образом: д;=1; а;=1'; а — число, изображаемое цифрами, полученными кодированием символов слова а, 0 аналогично получается из р, но при этом читается справа налево, т. е.
крайняя слева ячейка 11 содержит самый младший разряд, а крайняя справа — самый старший (это сделано для того, чтобы нули справа от 0 не влияли на значение р). Например, конфигурации 10110д,11011 соответствует четверка (22, 5, 1, 13) Выполнение команды преобразует конфигурацию К в следуюгдую конфигурацию К', при арифметизации этому соответствует преобразование четверки в новую четверку (а', дг а,'., 3'), Например, при команде дз1-«дзОР ранее приведенная конфигурация перейдет в К'=101100дз1011, которой соответствует четверка (44, 3, 1, 6).
Поэтому один шаг машины Т однозначно определяет отображение множества конфигураций в себя, т. е. печнсловую функцию ф,(К) =К'. Назовем ее функцией следующего шага. При введенной арифметизации этой функции соответствует четверка числовых функций следующего шага; иначе говоря, а', д', а', (1' — это числовые функции, каждая из которых зависит от четырех числовых переменных а, д, а, р.
Эти функции довольно простым об- 197 а' (а, д„ая 5) = та+ ~р, (до аг), если <р,, (до ат) = 1 (сдвиг вправо); 3 (а/т1, если <ра(дь а,) = О (сдвиг влево); (5.11а) Ч = Юч(Ч~ ат)1 (5.1 1б) г(т, (3), если ~ра(йо ат) = 1; (г(т,я), если гра(до ат) = О; (5.11в) (5.11г) тб+ <р,(до ат), если ~р,,(~уо ат) О; фт1, если ~ра (дь а,) = 1. Функции 1) и г, использованные здесь, определены в примере 5.11. Поскольку функции а', а', 5' построены из примитивно-рекурсивных функций с помощью примитивно. рекурсивного оператора условного перехода, а функция а' просто совпадает с примитивно-рекурсивной. функцией ~р„ то все они — примитивно-рекурсивные функции от четырех переменных а, д, а, б. Можно убедиться, что применение соотношений (5.11) к приведенной ранее в качестве примера четверке (22, 5, 1, 13) и команде да1-+дзО)с даст четверку (44, 3, 1, 5); напомним, что т=2, разом связаны с функциями системы команд ~р,ь ф,ь ~ра.
Действительно, д'=~р,; другие функции зависят еще и от сдвига. Если головка сдвинулась вправо, то это означает сдвиг цифр на разряд влево, т.е. увеличение числа а в т раз (напомним, что т — мощность алфавита А), и сдвиг цифр числа 5 на разряд вправо (так как они читаются справа налево), т.е. уменьшение числа (3 в т раз. Кроме того, в младший разряд а записывается символ, напечатанный на данном шаге, а младший разряд б становится обозреваемым символом. При сдвиге головки влево роли а и 13 меняются; а уменьшается, 5 увеличивается и т.д. Поэтому Итак, доказано, что на каждом шаге любая машина Тьюрннга осуществляет примитивно-рекурсивное вычисле- ние.
Переходим теперь к арифметизации общего поведе- ния машины. Пусть задана начальная конфигурация К(0) = (ао. о)о, ао, До). Тогда конфигурация, возникающая на такте 1, зависит от величины 1 и компонент ао, до, ао, йо началь- ной конфигурации, иначе говоря, она является векторной функцией К(Е) = (К, (1), К,(1), К,(1), Ко (1)), компоненты которой — векторные функции, зависящие от пяти пере- менных 1, ао, ао, ао, йо. Эти функции определяются следую- щим образом: К (О, а,, д,, ао, Ц,) = а,; К„(1+ 1,ссо, д,, а, ()о) = а' (К. (1, а„до,а„йо), (,1 ) К,((,ао,уо...бо). К.(...9о,;,Ь, К (1,,,9„а„р,)).
В соотношениях (5.126) — (5.12г) аргументы ао, до, ао, ро в функциях Ко для краткости опустим: К (О) =ао; Ко (( + 1) ~ 9 (Ка Ф Кд й~ Ко Ф Ко И))1 (5 126) К,(0) = а,; К, ((+ 1) = а' (К (1), К„(Г), К, (1), К~(()); (5.12в) Ко(О) =бо; К (1 + 1) = ~3' (Ка (О, Ко (Г), К, (1), К И)). (5.12г) Соотношения (5.12) формально выражают то очевидное обстоятельство, что координаты вектора К(1+1) одно- значно определяются координатами вектора К(1). Эти со.
отношения представляют собой схему примитивной рекур- сии, определяющую четыре функции К, Ко, Ко. Ка(ре- курсия ведется по переменной 1) с помощью функций а', а', а', $', примитивная рекурсивность которых уже доказа- на. Следовательно, функции Ко также примитивно-рекур- сивны, ,199 Остался последний шаг доказательства: рекурсивное описание результата работы машины Тьюринга.
Ограни- чимся для простоты правильно вычисляющими машинами (которые начинают с конфигураций вида а1аойо и останав- ливаются в конфигурациях вида д,а4,). Для таких машин К„(0)=0, К„(0)=1, исходное слово на ленте кодируется числом т[3о+ао, заключительное слово — числом т[3,+а,. Поэтому результат работы машины — это функция 1(тйо+ +ао) =т[3.+а,, Заключительное слово — это слово, напи- санное на ленте в тот момент 1,, когда машина впервые перешла в заключительное состояние а„т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
