Игошин Математическая логика и теория алгоритмов (1019110), страница 81
Текст из файла (страница 81)
Обратимся к примерам. Нетрудно понять, что машина Тьюринга из примера 32.2 по существу вычисляет функцию Т(х) = х+ 1, а машина Тьюринга из примера 32.3 вычисляет функцию Дх) = х — 2. Пример 32.5. Построим машину Тьюринга, вычисляющую функцию Т(х) = х/2. Эта функция не всюду определена: областью ее определения является лишь множество всех четных чисел. Поэтому, учитывая определение 32.4, нужно сконструировать такую машину Тьюринга, которая при подаче на ее вход четного числа давала бы на выходе половину этого числа, а при подаче нечетного — работала бы неограниченно долго.
Сконструировать машину Тьюринга — значит написать (составить) ее программу. В этом процессе два этапа: сначала создается алгоритм вычисления значений функции, а затем он записывается на языке машины Тьюринга (программируется). В качестве внешнего алфавита возьмем двухэлементное множество А = (О, Ц.
В этом алфавите натуральное число х изображается словом 1! ... 1, состоящим нз х единиц, которое на ленте машины Тьюринга записывается в виде х единиц, стоящих в ячейках подряд. Работа машины начинается из стандартного начального положения: 01...1а,10 (число единиц равно х).
Сделаем начало вычислительного процесса таким: машина обозревает ячейки, двигаясь справа налево, и каждую вторую единицу превращает в О. Такое начало обеспечивается следующими командами: (1) 911 чз!Л (2): дз! -+ 4,0Л; (3): д,О- д,ОЛ. Если число х елиниц нечетно, то машина продолжит движение по ленте влево неограниченно, т.е. будет работать бесконечно.
Если же число х единиц четно, то в результате выполнения команд созлается конфигурация д,0010101...01010, в которой число единиц равно х/2. Остается сдвинуть елиницы так, чтобы между ними не стояли нули. Для осуществления этой процелуры предлагается следующий алгоритм. Будем двигаться по ленте вправо, ничего на ней 325 не меняя, до первой единицы и перейдем за единицу. Передвиже- ние осуществляется с помощью следующих команд: (4): 9~0 -+ дзОП; (5): дзО -э ЧзОП; (6): чз! -+ ч«!П. В результате их выполнения получим конфигурацию ОО!9,0 10!О! ...
О!0100. (») Заменим О, перед которым остановились, на 1 и продвинемся вправо до ближайшего 0: (7): 940 -» 9,1П; (8): дз1 -+ дз1П. Получим конфигурацию 00111д,0101...010100, в которой пра- вее обозреваемой ячейки записаны «пары» 01, ..., 01.
Кроме того, на ленте одна единица записана лишняя. Продвинемся по ленте вправо до последней «пары» 01. Это можно сделать с помощью своеобразного цикла: (9): ФзО -+ В»ОП; (!О): 9,! ->9,!П.' Получим конфигурацию 001110101 ... 010109«00. Двигаться дальше вправо бессмысленно. Вернемся на две ячейки назад и заменим единицу из последней «пары» 01 на ноль: (11): 7»0 -+ Я~ОЛ; (12): дтО -+ 9,0Л; (13): г7,1 -э 9~0Л. Получим конфигурацию 001110101...019,00.
Число единиц на ленте снова равно х/2. Продвинемся влево на одну ячейку с помо- щью команды (14): д»0 — э д»ОЛ, В результате чего получим конфигурацию 001110101 ... 0!Осу»100. Теперь уничтожим самую правую единицу и продвинемся по лен- те влево до следующей единицы: (15): 9,! -+ дмОЛ; (16): 9мО -+ дмОЛПолучим конфигурацию ООП!О!О! ... 09„!ОО, (««) в которой левее обозреваемой ячейки записана серия пар 10, 1О, ..., 10 (если читать справа налево).
Теперь на ленте недостает одной единицы, т.е. число единиц равно (х/2) — 1. Продвинемся по ленте влево до последней «пары» 10. Это можно сделать с помощью цикла (17): дм1 -+ дп1Л; (18): 9пΠ— Д, ОЛ, выполнив который, придем к следующей конфигурации: 001дп110101...0100. Вернемся вправо к ближайшему нулю и превратим его в единицу: 326 (19): дп! -э дц1П; (20): рц1 — ~ рц1П' (21): дпΠ— > дц1П. Получим конфигурацию 00! 1! 19ц!О! ... 0100, в которой число единиц снова равно х/2. Если теперь перешагнем вправо по ленте через обозреваемую единицу и переведем машину в состояние 94 с помощью команды (22): рц1 -+ 941П то придем к следующей конфигурации: 0011111940! ...
0100, которая по существу аналогична конфигурации (е). В результате программа зацикливается (становится циклической): снова ближайший 0 превращается в 1, а самая правая 1 — в О, затем машина возвращается к самому левому нулю, оказываясь в начале следующего цикла, и т.д. Как же завершается работа программы? В некоторый момент конфигурация будет иметь вид 00111...11!Оды!00. Выполнив команды (17), (18), придем к конфигурации 00111...1дп110100. Далее выполняются команды (19), (20), (21), что приводит к конфигурации: 00111 ...! 111! 1рн00.
Остается остановить машину. Это делается с помощью команды (23): дцΠ— ~ доОЛ. Заключительная конфигурация имеет вид: 00111... 111!до!00. Запишем программу машины Тьюринга в табличной форме: Предлагается самостоятельно проследить за работой этой машины Тьюринга, взяв в качестве исходных конкретные слова: 111, 1!11, !!1111, 1!11111111. Правильная вычиелимость функций на машине Тьюринга. В предыдущем пункте мы рассмотрели вопрос о том, что значит и каким образом данная машина Тьюринга вычисляет функцию 327 7(хн х,, ..., х»)». Для этого нужно, чтобы каждое из чисел хо хп ..., х„было записано на ленту машины непрерывным массивом из соответствующего числа единиц, а сами массивы были разделены символом О.
Если функция Дх„хн ..., х„) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подрядны хы ..., х„) единиц. При этом мы не очень строго относились к тому, в каком начальном положении машина начинает работать (часто это было стандартное начальное положение), в каком завершает работу и как эта работа протекает.
В дальнейшем нам понадобится более сильное понятие вычислимости функции на машине Тьюринга — понятие правильной вычислимости. Онределение 32.б. Будем говорить, что машина Тьюринга правильно вычисляет функцию Дхн хн ., х„), если начальное слово а,01" 01" 0...01".0 она переводит в слово д»01Гы»" -"">0...0 и при этом в процессе работы не пристраивает к начальному слову новых ячеек на ленте ни слева, ни справа. Если же функция (" не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе работы не будет надстраивать ленту слева. Пример 32.7.
Приведем программы машин Тьюринга, правильно вычисляющих функции Ю(х) = х+ 1 и 0(х) = О. Функция 5(х) = х«1 осуществляет перевод: д,01"0 =» а»01" '. Ее программа: а10 -» азП, аг1 -+ аз1П, д»0 — » 4з1, аз1 » аз1Л, дзО -» а»0. Функция О(х) = 0 осуществляет перевод: д,01"0 =» д»00»» '. Ее программа: д~О -+ у,ОП, дз1 -+ йз1П, ййО -+ дзОЛ, йз1 -+ д«0, 440 -» -» йзОЛ, дзΠ— » а»О. Соответствующую машину Тьюринга обозначили О.
В Задачнике (М 12.24) разобрана работа машины А, называемой «леренос нуля», которая осуществляет перевод слова 001"0 в слово 01"00. Причем как в начальном, так и в заключительном состоянии обозревается первая левая ячейка с нулем. Пример 32.8. Построитьдве машины «левый сдвиг» Б и «нравый сдвиг» Б'. Первая из начального стандартного положения перерабатывает слово 01'О в то же самое слово и останавливается, обозревая самую левую ячейку с нулем. Вторая машина из начального состояния, в котором обозревается левая ячейка с нулем, слово 01 "0 перерабатывает в то же самое слово и останавливается, обозревая самую правую ячейку с нулем.
Программа машины Б: а10 -+ дзОЛ, аз! -» г7з)Л, дтО » а»0. Ясно, что программа машины Б' получается из программы предыдущей машины заменой символа «Л» символом «П». В задаче М» 12.27 Задачника требуется построить машину (называемую «транснозицией» и обозначаемую В), осуществляющую переход Ори,01 "0 =» О 1Уд»01»0. 328 Композиция машин Тьюринга. Опредееение 32.9. Пусть заданы машины Тьюринга О, и Оц имеющие общий внешний алфавит (а,, а„..., а ) и алфавиты внутренних состояний (9м дь ", Ч,) и (до, а', ..., а,') соответственно. Композицией (или произведением) машины й, на машину Оз называется новая машина О с тем же внешним алфавитом (ам аь ..., а ), внутренним алфавитом (дм 9„..., а„, д„, ь ..., а„„,) и пРогРаммой, полУчающейсЯ следУющим образом.
Во всех командах из О,, содержащих символ остановки дм заменяем последний на д„,, Все остальные символы в командах из О, остаются неизменными. В командах из Оз символ 9о оставляем неизменным, а все остальные состояния д (1= 1, ..., Г) заменяем соответственно на д„, о Совокупность всех так полученных команд образует программу машины-композиции О. Введенное понятие является удобным инструментом для конструирования машин Тьюринга.
Покажем это на примере. Пример 32.10. Сконструируем машины Тьюринга, правильно вычисляющие функции-проекторы 1„"(хь х,, ..., х„) = х (1 < т < и). Рассмотрим сначала конкретный случай и = 3, т = 2, т.е. функцию 1,'(хь хь хз) = х,. Мы должны переработать слово 9,01" 01" 01" 0 в слово доО!" О. Будем применять к начальной конфигурации последовательно сконструированные ранее машины Тьюринга Б', В, Б, О: 9,01.01.01.0; Б'. 01 901'*01'О; В: 01 901 01"О; Б'. 01'01 ~901'0; О: 01м01" 900"зО; Б: 01"'ч101мОО' 0; О: 01" 900" ОО" 0; Б: 901 00*~00.О.
Таким образом, функция 1тз(х„хь х,) = хз вычисляется следующей композицией машин: Б'ВБ'ОБ-ОБ- = Б'ВБ'(ОБ )~. Проверьте самостоятельно, что функция 1зг(хь хз) = хз вычисляется композицией Б'ВОБ . Теперь мы можем представить себе алгоритм построения композиции машин Б", В, Б, О для вычисления любой функции вида 1„"(хь хь ..., х„) = х„. С помощью правого сдвига Б', применив его т — ! раз, нужно сначала достичь массива 01кч (Б') -'. 01" 0...901"-0...0рьО.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
