Главная Промышленная автоматика.

1.6. ПРОСТЕЙШАЯ МОДЕЛЬ ВЫЧИСЛЕНИЙ: МАШИНА ТЬЮРИНГА

6) Qi- заключительное (или допускающее) состояние,

7) б - функция переходов, она отображает некоторое подмноже-

ство множества QxT* в Qx (Гх {L, R, S})*, т. е. по произвольному набору из состояния и k символов на лентах она выдает новое состояние и k пар, каждая из которых состоит из нового символа на ленте и направления сдвига головки.

Пусть 6(<7i, аь «2, . . ., ah)={q, {а\, di), (а;, d), . . ., (а*, d)) и машина Тьюринга находится в состоянии q, а ее головка на i-й ленте обозревает символ а;, Тогда за один шаг эта машина

Тьюринга переходит в состояние д, заменяет ai на а/ и сдвигает головку на г-й ленте в направлении (или в соответствии с) di.

Машину Тьюринга можно приспособить для распознавания языка. Символы на лентах такой машины включают алфавит рассматриваемого языка (его буквы играют роль входных символов), пустой символ, обозначаемый Ь, и, возможно, другие символы. Вначале на первой ленте записано слово из входных символов по одному на клетку, начиная с самой левой. Все клетки справа от клеток, содержащих входное слово, пусты. Все остальные ленты целиком пусты. Слово из входных символов допускается (воспринимается) тогда и только тогда, когда машина Тьюринга, начав

• ••

Ojblbj

Рис. 1.20. Работа машины Тьюринга над цепочкой 01110.



работу в выделенном начальном состоянии (головки при этом находились палевых концах своих лент), сделает последовательность шагов, которые в конце концов приведут ее в допускающее состояние. Языком, допускаемым данной машиной Тьюринга, называется множество всех слов из входных символов, допускаемых в описанном только что смысле.

Пример 1.8. Двухленточная машина Тьюринга на рис. 1.20 распознает палиндромы ) в алфавите {О, 1} следующим образом.

1) Первая клетка налейте 2 отмечается специальным знаком х, и вход копируется с ленты 1, где он записан вначале (рис. 1.20, а), на ленту 2 (рис. 1.20,6).

2) Затем головка на ленте 2 сдвигается к х (рис. 1.20, в).

3) Повторяется такая процедура: головка на ленте 2 сдвигается вправо на одну клетку, а на ленте 1 - влево на одну клетку и соответствующие символы сравниваются. Если все символы совпадают, то вход является палиндромом и машина Тьюринга доходит до допускающего состояния q. В противном случае в некоторый момент очередной шаг машины Тьюринга будет не определен, а она остановится, не допустив входного слова.

Функция переходов соответствующей машины Тьюринга приведена на рис. 1.21. □

Работу машины Тьюринга формально можно описать с помощью "мгновенных описаний". Мгновенным описанием (МО) -ленточной машины Тьюринга М называется набор (ai, а, . . ., a,), где для каждого i представляет собой слово вида xqy, причем ху - слово на 1-й ленте машины М (пустые символы, стоящие справа от его правого конца, опускаются), а q - текущее состояние машины. Головка на 1-й ленте обозревает символ, стоящий справа от q.

Если мгновенное описание Di переходит в мгновенное описание за один шаг машины Тьюринга М, то пишут Di [-jD а (знак 1-читается "переходит в"). Если Daf-ж • • • Нжп Для некоторого л>2, то пишут Di-"!iiD„. Если либо D=D, либо D\-%iD, то пишут D\-liD.

Данная й-ленточная машина Тьюринга М = (Q, Т, I, б, Ь, q, qf) допускает слово aia. . . «п, где at - элементы из /, если {q„ai а. . . ?о. <?о.....<7о) Км («1. «2, . - ., «й) для некоторых о,, содержащих qi.

Пример 1.9. На рис. 1.22 приведена последовательность мгновенных описаний машины Тьюринга, изображенной на рис. 1.21, ко-

Палиндромом называется слово, совпадающее с самим собой при чтении с конца, например 0100010.



Символ на ленте 1 ленте 2

Новый символ, сдвиг головки

лента 1

лента 2

Примечания

0, S

1, S b, S

X, R X, R b, S

«71

Если вход непуст, то на ленте 2 печатается X и головка сдвигается вправо; машина переходит в состояние qx-В противном случае машина переходит в состояние <75.

0, R

1, R Ь, S

0. R

1, R Ь, L

Ял «71

Машина остается в состоянии Qx и переписывает ленту 1 на ленту 2, пока на ленте 1 не встретится Ь. Затем она переходит в состояние q..

Ь, S Ь, S Ь, L

0, L

1, L

X, R

«72

«73

Головка на ленте I остается на месте, а на ленте 2 движется влево до X Затем машина переходит в состояние (?з.

0, S

1, S

0, R

1, R

?4 й»

О, L

0. L

1, L I. L

0. S

1. S

0, S

1. S

0, S

1, S Ь, S Ь, S

«73 9з 9з ?з

«75

Состояния дз и q чередуются. В ?з сравниваются символы на обеих лентах, головка на ленте 2 сдвигается вправо и машина переходит в<74. Из <74 0на переходит в 95 и допускает входное слово, если головка достигла b на ленте 2. Если же не достигла, то головка на ленте I сдвигается влево и машина возвращается в состояние Чередование £/, и ?4 предотвращает уход головки на ленте 1 за ее левый коней.

Входное слово допускается

Рис. 1.21. Функция переходов машины Тьюринга распознающей палиндромы.





0 1 2 3 4 5 6 7 8 9 [10] 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0022