Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 33
Текст из файла (страница 33)
Не теряется ли при этом общность? Действительно, возможны другие определения вычисления: например, можно в заключительной конфигурации допускать символы из промежуточного алфавита А«р, а результатом считать слово в Ар... которое получится, если символы из А„выкинуть и «сдвинуть» оставшиеся куски. В частности, если А„,=-(1), то результатом будет число, равное числу единиц на ленте в заключительной конфигурации.
Оказывается, что потери общности не происходит; в частности, если функция вычислима в последнем смысле, то она правильно вычислима. Не будем заниматься детальным доказательством этого утверждения в общем виде, однако проиллюстрируем его справедливость на примерах (см. далее пример 5.7). Поэтому обычно прилагательное «правильный» будем опускать и говорить просто о функциях, вычислимых по Тьюрингу. Пример 5А. а.
Сложение. Во введенном ранее представлении чисел сложить числа а и Ь вЂ” это значит слово !' ° 1ь переработать в слово 1'~ь, т. е. удалить разделитель ° и сдвинуть одно из слагаемых, скажем первое, к другому. Это преобразование осуществляет машина Т+ с четырьмя стояниями и следующей системой команд (первая манда введена для случая, когда а=О и исходное слово имеет вид 1"): В этой системе команд перечислены не все сочетания состояний машины и символов ленты: опущены те из них, которые при стандартной начальной конфигурации никогда не встретятся.
Опускать ненужные команды будем в дальнейшем; в таблицах это будет отмечено прочерками. Диаграмма переходов Т+ приведена иа рнс. 5.3; заключительное состояние отмечено двойным кружком. б. Ко пиров а н не (перезапись) слова, т. е. переработка слона а в и и. Для чисел эту задачу решает ма шина Т„, система команд которой приведена в табл, 5.1. Таблица 6.1 Чв61в ЧвИ Чв1вв Чв1Е ЧвХВ1 Чз !7 Чв!1. Чвв 1 Чз 11 Чв1Ь .Ч1 Чв Чв Чв Чв" й 11 — 760 ' 161 Диаграмма переходов Т„„дана на рис.
5А. На этой диаграмме (а также последующих) приняты сокращения: 1) если нз Чв в Ч; ведут два ребра с одинаковой правой частью, то они объединяются в одно ребро, на котором левые части записаны через запятую; 2) если символ на ленте не изменяется, то он в правой части команды не пишется. На петле в Ч, использованы одновременно оба сокращения. Машина Т „при каждом проходе исходного числа 1" заменяет левую нз его единиц нулем и пишет (в состоянии Чз) одну единицу справа от 1' в ближайшую пустую клетку. При первом проходе, кроме того, в состоянии Чв ставится маркер. Таким образом, копия 1' строится за а проходов, После записи очередной единицы машина переходит в со- стояние ои которое передвигает головку влево от ближайшего нуля, после чего машина переходит в д, и цикл повторяется.
Он прерывается, когда о1 обнаруживает на ленте Риа 6.4 не единицу, а маркер. Это значит, что все единицы 1' исчерпаны, т. е. сделано а проходов. Тогда головка возвращается влево в свое исходное положение, заменяя по дороге все нули единицами. Некоторые операции над машинами Тьюринга. Работа машины Тьюринга полностью определяется исходными дан. ными и системой команд. Однако для понимания того, как конкретная машина решает данную задачу, как правило, возникает потребность в содержательных пояснениях типа тех, которые приводились для машины Т„. Эти пояснения часто можно сделать более формальными и точными, если использовать блок-схемы и некоторые операции над машинами Тьюринга.
Напомним, что композицией двух функций 11(х) и 1з(у) называется функция д(х) 1»()1(х)), которая получается при применении )з к результату вычисления )ь Для того чтобы д(х) была определена при данном х, необходимо н достаточно, чтобы 11 была определена на х и 12 была определена на 11(х). Теорема 5.1, Если ),(х) и (т(у) вычислимы по Тьюрингу, то их композиция~рЦ»(х)) также вычислима по Тьюрингу. Пусть Т» — машина, вычисляющая 1ь а Те —. машина, вычисляющая (м н множества их состояний соответственно Я~=(дн, ..., д»»,) и Я»=(дм, ..., о»„). Построим диаграмму переходов машины Т из диаграмм, Т, и Тз следующим образом: отождествим начальную вершину дм диаграммы машины Т, с конечной вершиной дм диаграммы машины Т, 162 (для систем команд это равносильно тому, что систему команд Тэ приписываем к системе команд Т, и при этом <», в командах Т< заменяем на <1»).
Получим диаграмму с а>+ +па — 1 состояниями. Начальным состоянием Т объявим <»<, а заключительным — <>„. Для простоты обозначений будем считать 1< и ~з числовыми фУнкциЯми одной пеРеменной. Пусть 1>(1>(х) ) определена. Тогда Т>(1") =1> <"'> и д«1"=Р т, с~д<,1> <">. Машина Т пройдет ту же последовательность конг, фигураций с той разницей, что вместо <»,1> <"> она перейдет в <1»1> <">. Эта конфигурация является стандартной начальной конфигурацией для машины Ть поэтому <1><1> < > =~ т, ~<>ы15<> <"».
Но так как все команды Т, содержатся в Т, то т, <1»1 '=>-<»<1> <"'> =ьд„15<6 <'» и, следовательно, Т(1") = г г 15<5! и . Если же (з()'<(х)) не определена, то Т, или Тэ не остановится н, следовательно, машина Т не остановится. Итак, машина Т вычисляет(з(1>(х)). О) Построенную таким образом машину Т будем называть ко>япозицией машин Т< Т, и Т, и обозначать Т,(Т,), а также изображать блоксхемой (рис.
5.5). Эта блоксхема имеет более точный смысл, чем изображенная на рис. 5.2, так как она всегда предполагает, что исходными данными машины Т> являются результаты Т>. При этом они уже «готовы к употреблению», так как благодаря правильной вычнслимости (которая существенна прн композиции) заключительная конфигурация Т, легко превращается в стандартную начальную конфигурацию Т,, Поскольку машина Тьюринга вектор над А„,„воспринимает как слово в алфавите А„,0( '), определение композиции и теорема 5.1 остаются в силе, если Т< и Т, вычисляют функции от нескольких переменных. Важно лишь, чтобы данные для Т, были в обусловленном виде подготовлены машиной Т,.
Это видно на следующем примере. Пример 5.5. Машина, диаграмма которой приведена на ис. 5.5, — это машина Т+(Т„,„). Она вычисляет функцию (х) =2х для хФО; при этом машина Т„, строит двухкомпонентный вектор, а Т+ вычисляет функцию от двух переменных, 11ь Для удобства последующих построений установим следующий важный факт. Оказывается, что для вычисления на машине Тьюринга достаточно, чтобы лента была бесконечной только в одну сторону, например вправо.
Такая лента называется правой полулентой. Теорема 5.2. Любая функция, вычислимая по Тьюрингу, вычислима на машине Тьюринга с правой полулентой; Рис. б.б иначе говоря, для любой машины Тьюринга Т существует эквивалентная ей машина Ти с правой полулентой. Аналогичная теорема формулируется для левой полулеиты. Можно предположить по крайней мере две идеи построения такой эквивалентной машины: 1) всякий раз, когда головке прежней машины надо зайти за левый край ленты, новая машина предварительно сдвинет все написанное (вместе с головкой) на клетку вправо; б) лента «перегибается пополам»; при этом ячейки правой половины прежней ленты размещаются, скажем, в нечетных ячейках полуленты, а ячейки левой половины — в четных.
Первая идея реализована в (471; реализация второй предлагается- как упражнение. П Рассмотрим теперь вычисление предикатов на машинах Тьюринга. Машина Т вычисляет предикат Р(а). (сс — слово в А„,„), если Т(а) =си, где сз=И, когда Р(а) истинно, и сэ=л, когда Р(а) ложно. если же Р(а) не определен, то машина Т, как и при вычислении функций, не останавливается. При обычном вычислении предиката уничтожается а, что может оказаться неудобным, если после Т должна работать другая машина. Поэтому введем понятие вычисления с восстановлением: машина Т вычисляет Р(а) с восста- 164 новлением, если Т(а) =ви. Если существует машина Т, вычисляющая Р(и), то существует и Т, вычисляющая Р(и) с восстановлением.
Действительно, вычисление с восстановлением можно представить следующей последовательностью конфигураций: д~а=~д„, а + и~а ° д„,а=~а ° и,, ы=:-д,,ак. Первая часть этой последовательности реализуется машиной Т„,, вторая — простым сдвигом головки до маркера «, третья — машиной Тю вычисляющей Р(а) на правой полуленте (одного копирования мало для восстановления, так как копию может испортить основная машина Т; нужна машина, не заходящая влево от и), четвертая — переносом ы в крайнее левое положение. Машина Т является композицией указанных четырех машин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
