С.В. Яблонский - Введение в дискретную математику (1060464), страница 19
Текст из файла (страница 19)
Введенные нами устройства, работающие над конечными входными последовательностями, можно трактовать гл. а вычислпмыв функции также в виде «машины». Она состоит из бесконечной вправо ленты и автомата (см. рнс. 2). Бесконечная лента разделена на ячейки, которые нумеруются натуральными числами 1, 2, ...; в ячейки 1, 2, ..., 1 вписываются символы а(1), а(2), ..., а(1) из алфавита (О, 1, ..., У вЂ” 1). Автомат обладает головкой н может находиться в одном ~- аФлаиав Рис.
2 из (конечного числа) состояний х„;, х,. Головка в каждый из моментов времеви $ (1 1, 2, ...) обозревает одну ячейку ленты (при Г 1 обозревается 1-я ячейка); по символу, прочитанному на ленте, и по внутреннему состоянию автомат вырабатывает новое состояние и некоторый символ, который через головку вписывает в ту же ячейку (в начальный момент 1=0 состояние автомата есть х,). После этого головка сдвигается по ленте па одну ячейку вправо и т. д.
Машина останавливается при появлении в поле зрения головки символа Л, и на ленте в ячейках 1, 2, ..., 1 получается выходная последовательность (у(1), ((2), ..., ((1)). Работу этой машины можно задать при помощи так называемой программы, т. е. специальной таблицы (см. табл. 1). В данной таблице строки занумерованы символами Л, О, 1, ..., У вЂ” 1, а столбцы — символами х„..., х.. Строка, соответствующая символу Л, оставляется незаполненной. В клетку, расположенную в строке и (итьЛ) и в 1-м столбце, вписывается тройка символов (г (а, х~), В, 6(а, х,)). Эта тройка называется коаандой.
Машина выполняет команду следующим образом: если головка обозревает на ленте символ а и машина к атому моменту находится в состоянии хь то в рассматриваемый момент в ячейку вместо символа а записывается символ Р(а, х,), а машина переходит в состояние б(а, х~) и передвигает головку $$6 ч. г, ФункцпонАльные системы с опеРАцпями по ленте на одну ячейку вправо (В). Если читаемым символом является символ Л, то в соответствующей клетке таблицы стоит «пустая» команда, что рассматриваетсл как команда остановки машины. Очевидно, что программа машины полностью определяется каноническими уравнениями для ф(х).
Твблвнв Данный тпп машин можно обобщить, допуская более ' широкий класс программ и более сложное взаимодействие автомата с лентой. Так, приведенная на рпс. 3 машина (обозначим ее через зл) состоит нз бесконечной (но уже в обе сторо- -1 -101 Ф Рвс. 3 ны) ленты и автомата (см. Рис. 3). Ячейки ленты нумеруются целыми числами ..., -~, ..., — т, О, т, ..., 3, ..., в ячейки вписываются символы из алфавита (О, т, ... ..., Й вЂ” () (О в дальнейшем будет играть также роль пустого символа); автомат обладает головкой, способпой гл. 4.
Вычислимык Фуккцпи совершать один из актов: Л вЂ” сдвигаться на одну ячейку вправо, Р— сдвигаться па одну ячейку влево и Ю вЂ” продолжать обозревать ту же ячейку. Символы яо ..., я, обозкачагот состояния автомата. Работа машппы И характеризуется программой Т (см. табл. 2).
В пей часть клеток может быть иезаполненвой, т. е. содержать пустые Табаева 2 ебх команды, а остальная часть заполняется тройками символов, представляющими команды машины. Например, в клетку,' расположенную в строке с номером а и 1-и столбце (см. табл. 2), вписана тройка сРх. В команде: с — символ па алФавита (О, 1...„й — 1), Р— символ из алфавита (Л, Ь, Я и х — одно пз состояний (ко ..., х,). Пусть головка машины обозревает символ а, находясь в состояиип хь тогда: а) если в клетке (а, к>) находится команда (сРх), то машина заменит в атой ячейке символ а на с, перейдет в состояние я, осуществит движение Р и приступит к выполнеиию следующей команды; б) если в клетке (а, к~) стоит пустая команда, машина останавливается. В начальный момент головка установлена над некоторой ячейкой ленты (качальной ячейкой) и машина находится в состоянии х, (соответствующем левому столбцу программы Т).
Таким образом, машина, начиная из исходной ситуации (качального состояния и начальной ячейки), осуществляет переработку исходной записи иа ленте в соответ- П8 ч. ь ФункцпонАльные спстемы с ОпеРАциями не появится — машина не остановится. Введенные нами машины называются машинами Тьюринга. Пример 1. Пусть й 2. Рассмотрим машину, которая в произвольной ааписн, начиная из любой ячейки, двигаясь вправо, находит первый нуль: 1ян1 Очевидно, она моятет быть вадана программой, записанной в табл. 3. В самом деле, возможны три случая.
1) В начальный момент .оловка видит символ О. Машина сразу останавливается. 2) В начальный момент головка видит сиьгвол $ и справа от начальной ячейки запись содержит хотя бы один О. Машина переместит головку через массив из единиц вправо и остановится над первым нулем. 3) В начальный момент головка видит символ $ и справа от начальной ячейки вались состоит сплошь из единиц. Машина будет перемещать головку через массив единиц вправо, не останавливаясь. Теперь введем ряд обозначений и понятий, связанных с записью на ленте. Будем изображать при помощи стрелки положение головки на ленте в рассматриваемый момент времени (см.
рис. 4). То же можно записать еще и так1 а а, Здесь стрелка относптся к символу а„расположенному непосредственно левее стрелки, и обозначает, что головка в данный момент обозревает символ а,. Если лента заполнена сплошь нулями, то иногда будем говорпть, что мы имеем Пустую ленту.
Для ячейки, ствии с программой Т. Имеются две возможности: а) прн работе машины появится пустая команда — машина останавливается и мы получаем заключительную вались на ленте (состояния, в которых машина останавливается, будем нааывать ганлючительнььви); Таблица 3 б) при работе машины пустая команда $19 гл.
и вычпслимыв этпкции в которой эаппсан символ О, будет употребляться также термин нустая ячейки Наконец, совокупность ячеек, которые посетит головка, двигаясь из начальной ячейки до данного момента Г, называется рабочей зоной ленты в момент времени й В дальнейшем нам придатся строить машины Тьюринга, обладающие опре- деленными специфическими свонствами. При этом удобно строить машины, исходя иэ уже построенных машин. Для этого иы введем принцип двойственности и два типа композиции машпн.
Принцип двойственности для программ (машин). Пусть Т вЂ” произволь- к, а, а, и машина Б в момент г ее переработала в запись (2) с,с,...с,..., то машина Й» аапись .. ага~ имеющуюся в начальный момент и симметричную (т) ная программа. Обоэначим через Т» программу, которая получается из Т, если всюду в Т эаменить в командах В на Ь и Ь на В. Программа Т» называется двойственной к Т. Пример 2. Программа Т», эадаваемая табл.
4, очевидно, будет двойственной к программе Т ив предыдущего примера. Очевидно, что (Т»)» Т, т. е. понятие двойственности программ является взаимным. В последующем мы будем также машины И и ЮР, соответствующие программам Т и Т», наэывать двойственными машинами. Легко видеть, что двойственные машины % и Й» в некотором смысле функционируют симметричным обрааом, а именнш если в начальный момент на ленте имеется вались 12О ч. 1.
сьункцнонйльные системы с опекйциями относительно а„перерабатывает в момент 1 в запись ... с.. сес,..., (4) симметричну1о (2) относительно с,. Например, программа Т«(см. пример 2) в силу этого замечания должна, двигаясь влево, отыскивать первый нуль, в чем также можно убедиться непосредственной проверкой.
1-й тип композиции — последовательное подключение одной машины к другой. Пусть Б«и х))т — две Таблице 5 произвольные машины Тьюрлнга пад одним и тем же входным алфавитом (О, 1, ..., )с — 1), мнохсества состояний которых не пересекаются. Перенумеруем числами О, 1, 2, ..., ) — 1 все пустые клетки (команды) программы Т« машины эт),. Пусть р(х) — произвольный предикат«) на множестве (О, 1, 2, ..., ) — 1). Построим машину йч, которую и будем называть последовательныы подключениеы машины й, к 2)), (относптельно предпката Р(х)). Для этого из таблиц Т, и Т, машин И«и й, построим новую таблицу Т (см.
табл. 5). В ней первая половина совпадает с таблицей Т. для тех клеток пз Т„ в которых стоит непустая команда. В тех клетках т), для которых р(т)) = 1, Р в таблице Т стопт команда пан~ (где а — номер строки, в которой находится эта клетка ц, а нт — начальное состояние вташпны И,). В тех клетках ц, для которых р(ц)' О, в таблице Т стоит такясе пустая команда. Вторая половина таблицы Т полностью совпадает с таблицей Т,. «) Предыывт р(х) ыв (О, 1, ..., 1 — П вЂ” специальная фуыкцыя ыв Рь В двльыейшеы встречаются д«ух«вечные ы трех«не«мне ыредыквтм. Оыы соответствсыыо врзыыыюот выачеыыя ыэ ыысжесхв (О, П ы (О, 1т 2).
121 гл. ь вычислпмыв функции Очевидно, что работа машины й состоит в следующем: исходная запись ленты сначала перерабатывается машиной Им и если машина И, заканчивает работу на команде Ч такой, что р(т)) = 1, то содержимое ленты перерабатывается машиной й,. При этом начальной ячейкой для машины И, будет ячейка, в которой остановилась машина И,. Таким образом, машина И в некотором смысле осуществляет последовательную работу машин И, и И,. 2-й тип композиции — итерация машины. Пусть И,— произвольная машина Тьюринга и числами О, 2, ., ! — 1 аанумерованы пустые клетки ев программы Т,. Пусть р(х) — произвольный предпкат на множестве (О, 1, 2, „! — 1).
Построим машину И, которую будем называть итерацией машины И, относительно предината р(х). Для этого по таблице Т, построим таблицу Т машины И. Таблица Т совпадает с Т, вне клеток, являющихся пустыми для Т,. В тех клетках ц таблицы Т„для которых р(ц) О, в таблице Т стоит команда аЯн, (где а — номер строки, в которой находится эта клетка ц, а к, — начальное состояние машины й,).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
