Игошин Математическая логика и теория алгоритмов (1019110), страница 80
Текст из файла (страница 80)
Далее, конфигурация (2) за- 320 писывается так: 101д~О, конфигурация (3) — 1010д20 и, нако- нец, (4) — 10!Од»1. Вся последовательность записывается так: !Оу,1 =» 10!д|0 =» 1010д20 =» !О!Од»1. Приведем последовательность конфигураций при переработке этой машиной слова 1 101 1, исходя из начального положения, при котором в состоянии д, обозревается крайняя левая ячейка, в которой содержится символ этого слова (самостоятельно проанализируйте каждый шаг работы машины, указывая, какая команда обусловила его): д1 (2) (3) д2 (4) (5) (6) до Более короткая запись этой последовательности конфигураций, т е. процесса работы машины, будет д,1! 011 =» 1д,1011 ~ 11д,011 =» =» ! 10д211 =» ! 101д21 =» 11О! 1дзО ~ 11011д»1.
Таким образом, слово 11011 переработано машиной в слово 110111, Пример 32.2. Машина Тьюринга задается внешним алфавитом .ч = (О, 1, ш) (как и в предьиущем примере 0 — символ пустой ячей«и), алфавитом внутренних состояний Д = (до дь дь дз) и проРаммои: д,О -+ д10Л, дзО » дз1П, дзО -» д10Л, д,1 — » д,ОЛ, й! » н д21Л, дз! — » дн!П, д~» + д»0 дз" + дз*Ли дз* + дз»П. ! И ошин 321 Посмотрим, как эта машина перерабатывает некоторые слова, и постараемся обнаружить закономерность в ее работе. Предварительно заметим, что программа машины может быть записана также в виде следующей таблицы: Чтобы определить по таблице, что будет делать машина, находясь, например, в состоянии дз и наблюдая в обозреваемой ячейке символ 1, нужно найти в таблице клетку, находящуюся на пересечении столбца зз и строки, содержащей !.
В этой клетке записано дз1Л. Это означает, что на следующем шаге машина останется в прежнем состоянии дз, сохранит содержимое обозреваемой ячейки 1 и перейдет к обозрению следующей левой ячейки на ленте. Применим эту машину к слову!! *! 1. Вот последовательность конфигураций, возникающих в процессе работы машины (исходная конфигурация — стандартная начальная): 11» !аз! ~ 11» дз10 =» 11дз» 10 =» 1дз!» 10 =» аз!1» 10 =» дз011:» 10 =» =» аз!1 * 10 =» !!аз!» 10 =» 111дз» 10 =» 111 * дз10 ~ 111 * 1дзО =» ~ 111» д~10 ~ 111дз» 00 =» 11дз!» 0 ~ ! аз!1» 0 =» дз111» 0 ~ =» Чз0111 * 0 =» !аз!11 * 0 ~ 11~?з11 * 0 =» 111Чз1 * 0 ~ 1111Чз * 0 =» =» 1! 11» дзО =» 1111!!1» 0 =» 1! 11д»00. Предлагается проверить самостоятельно, что данная машина Тьюринга осуществляет следующие преобразования конфигураций: ! 1 * дз! =» 111д»0; 1 * ! 11д1! ~ 11111д»0; ! 1 * 11д, ! ~ 11111д»0; 11111» 1911 ~ 11111119»0. Нетрудно заметить, что данная машина Тьюринга реализует операцию сложения: в результате ее работы на ленте записано подряд столько единиц, сколько их было всего записано по обе стороны от звездочки перед началом работы машины.
Этот маленький опыт работы с машинами Тьюринга позволяет сделать некоторые выводы. Так тщательно описанное устройство этой машины (разбитая на ячейки лента, считывающая головка) по существу не имеет никакого значения. Машина Тьюринга — не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита А Ц Д, т.е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние. Конструирование машин Тьюринга.
Создание (синтез) машин Тьюринга (т.е. написание соответствующих программ) является 322 ~адачей значительно более сложной, нежели процесс применения данной машины к данным словам. Пример 32.3. Попытаемся построить такую машину Тьюринга, которая из л записанных подряд единиц оставляла бы на ленте л-2 единицы, также записанные подряд, если и > 2, и работала бы вечно, если п = О или и = 1. В качестве внешнего алфавита возьмем двухэлементное множество А = (О, 1). Количество необходимых внутренних состояний будет определено в процессе составления программы.
Считаем, что машина начинает работать из стандартного начального положения, т. е. когда в состоянии д, обозревается крайняя правая единица из л записанных на ленте. Начнем с того, что сотрем первую единицу, если она имеется, перейдем к обозрению следующей левой ячейки и сотрем там единицу, если она в этой ячейке записана. На каждом таком переходе машина должна переходить в новое внутреннее состояние, ибо в противном случае будут стерты вообще все единицы, записанные подряд. Вот команды, осуществляющие описанные действия: д,1 — з дзОЛ; дз1 — з дзОЛ.
Машина находится в состоянии дз и обозревает третью справа ячейку из тех, в которых записано данное слово (л единиц). Не меняя содержимого обозреваемой ячейки, машина должна остановиться, т.е. перейти в заключительное состояние д„независимо от содержимого ячейки. Вот эти команды: Чзб -+ ЧоО'* Чз) -з Чо). Теперь остается рассмотреть ситуации, когда на ленте записана всего одна единица или не записано ни одной.
Если на ленте записана одна единица, то после первого шага (выполнив команду д,1 -о дзОЛ) машина будет находиться в состоянии дз и будет обозревать вторую справа ячейку, в которой записан О. По условию, в таком случае машина должна работать вечно.
Это можно обеспечить, например, такой командой: дзО -+ дзОП, выполняя которую шаг за шагом, машина будет двигаться по ленте неограниченно вправо (или протягивать ленту через считывающую головку справа налево). Наконец, если на ленте не записано ни одной единицы, то машина, по условию, также должна работать вечно. В этом случае в начальном состоянии д, обозревается ячейка с содержимым О, и вечная работа машины обеспечивается следующей командой: д,Π— з д,ОП.
323 Запишем составленную программу (функциональную схему) построенной машины Тьюринга в виде таблицы: В заключение отметим следующее. Созданная нами машина Тьюринга может применяться не только к словам в алфавите А = (О, Ц, представляющим собой записанные подряд л единиц (л > 2). Она применима и ко многим другим словам в этом алфавите, например (проверьте самостоятельно) к словам: 10!1, 10011, 111011, 1!011, 1100111, !001111, !0111, 10110!11, 10010111 и т.д.(исходя из стандартного начального положения).
С другой стороны, построенная машина не применима (т.е. при подаче этих слов на вход машины она работает вечно) не только к слову «1» или к слову, состоящему из одних нулей. Она не применима и к следующим словам (проверьте самостоятельно): 101, !001, 11101, 101!01, 1!00101101 и т.д. Вычислимые по Тьюриигу функции. Определение 32.4. Функция называется вычислшиой ло Тьюрингу, если существует машина Тьюринга, вычисляющая ее, т.е.
такая машина Тьюринга, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функция для данного набора значений аргументов не определена. Остается договориться о некоторых условностях для того, чтобы это определение стало до конца точным. Во-первых, напомним, что речь идет о функциях (или возможно о частичных функциях, т.
е. не всюду определенных), заданных на множестве натуральных чисел и принимающих также натуральные значения. Вовторых, нужно условиться, как записывать на ленте машины Тьюринга значения хп хь ..., х„аргументов функции ~(хп х,, ..., х„), из какого положения начинать переработку исходного слова и, наконец, в каком положении получать значение функции.
Это можно делать, например, следующим образом. Значения хп хн ..., х„аргументов будем располагать на ленте в виде следующего слова: О 1 ... 1 О 1 ... 1 О ... О 1 ... ! О. х~ хз х„ Здесь полезно ввести следующие обозначения. Для натуральногох обозначаем: 1" = 1 ... 1, 0" = 0 ... О. х х Дополнительно полагаем 0' =! ' = л — пустое слово. Так что на слова 1» = Л, ! ' = 1, 1з = 11, 1' = ! 11, ... будем смотреть как на «изображения» натуральных чисел О, 1, 2, 3, ... соответственно. 324 Таким образом„предыдущее слово можно представить следующим образом: 01" О!" 0„,01 О. Далее, начинать переработку данного слова будем из стандартного начального положения, т.е.
из положения, при котором в состоянии а, обозревается крайняя правая единица записанного слова. Если функция Т(хь х,, ..., х„) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд Т(хь х„..., х„) единиц; в противном случае машина должна работать бесконечно. При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную 4ункцию. Таким образом, сформулированное определение 35.4 становится абсолютно строгим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
