Работа машины Тьюринга
Работа машины полностью определяется заданием в первый (начальный) момент: 1) слова на ленте, т. е. последовательности символов, записанных в клетках ленты (слово получается чтением этих символов по клеткам ленты слева направо); 2) положения головки; 3) внутреннего состояния машины. Совокупность этих трех условий (в данный момент) называется конфигурацией (в данный момент). Обычно в начальный момент внутренним состоянием машины является q1, а головка находится либо над первой слева, либо над первой справа клеткой ленты. Заданное слово на ленте с начальным состоянием q1 и положение головки над первым словом называется начальной конфигурацией. В противном случае говорят, что машина Тьюринга не применима к слову начальной конфигурации. Другими словами, в начальный момент конфигурация представима в следующем виде: на ленте, состоящей из некоторого числа клеток, в каждой клетке записан один из символов внешнего алфавита A, головка находится над первой слева или первой справа клеткой ленты и внутренним состоянием машины является q1. Получившееся в результате реализации этой команды слово на ленте и положение головки называется заключительной конфигурацией. Например, если в начальный момент на ленте записано слово a1a2ᴧa1a1, то начальная конфигурация будет иметь вид:
(под клеткой, над которой находится головка, указывается внутреннее состояние машины). Работа машины Тьюринга состоит в последовательном применении команд, причем, применение той или команды определяется текущей конфигурацией. Так в приведенном выше примере должна применится команда с левой частью q1a1. Итак, зная программу и задав начальную конфигурацию, полностью определяем работу машины над словом в начальной конфигурации. Если в работе машины Тьюринга в некоторый момент t выполняется команда, правая часть которой содержит q0, то в такой момент работа машины считается законченной, и говорят, что машина применима к слову на ленте в начальной конфигурации. В самом деле, q0 не встречается в левой части ни одной команды – этим и объясняется название q0 «заключительное состояние». Результатом работы машины в таком случае считается слово, которое будет записано на ленте в заключительной конфигурации, т. е. в конфигурации, в которой внутреннее состояние машины есть q0. Если же в работе машины ни в один из моментов не реализуется команда с заключительным состоянием, то процесс вычисления будет бесконечным. В этом случае говорят, что машина не применима к слову на ленте в начальной конфигурации.
3. Примеры машин Тьюринга, работающих в алфавите {a, b}
Пример 1. Построить машину Тьюринга T1, которая применима ко всем словам с внешним алфавитом {a,b} и делает следующее: любое слово x1x2...xn, где xi = a или xi = b (i =1,2,...n) преобразует в слово x2...xn x1, т. е., начиная работать при слове x1x2...xn на ленте в начальной конфигурации, машина остановится, и в заключительной конфигурации на некотором участке ленты будет записано слово x2...xn x1, а все остальные клетки ленты (если такие будут) окажутся пустыми. Решение. За внешний алфавит машины T1 возьмем множество A ={ᴧ,a,b}, а за внутренний – Q ={q0,q1,q2 ,q3}. Команды определим следующим образом:, q1a→ᴧПq2, q1b→ᴧПq3; qiy → yППi, где yÎ{a,b}, i = 2,3; q2 ᴧ→aHq0, q3 ᴧ→bHq0 Рассмотрим работу машины T1 над словом ba. В работе машины над словом ba начальная конфигурация имеет следующий вид:
На первом шаге действует команда: q1b→ᴧПq3. В результате создается следующая конфигурация: 3 x+9cHxrxfsNQmrQ5vZogmQFSQwCPTdZIj52uZJPT2TCsvvcCU890GUM8k6o/Y5pKH6gLbPW8+a7o olbp9ChJAeUOybTQdzZOIh5qsB8pabGrc+o+bJgVlKgXGgW5SsfjMAbRGE+mIzTsuac49zDNESqn npL+uPRxdPrKblC4SkZSg8J9JoecsVsjN4fJCuNwbseoX/O/+AkAAP//AwBQSwMEFAAGAAgAAAAh AFwwi4LdAAAACwEAAA8AAABkcnMvZG93bnJldi54bWxMT8tOwzAQvCPxD9YicUGtTVIgCnEqVMEB iSKRwt2JlyQlXkex24a/ZznBbWdnNI9iPbtBHHEKvScN10sFAqnxtqdWw/vuaZGBCNGQNYMn1PCN Adbl+VlhcutP9IbHKraCTSjkRkMX45hLGZoOnQlLPyIx9+knZyLDqZV2Mic2d4NMlLqVzvTECZ0Z cdNh81UdHOc+ztn4Ub9s9s/VVb1PXqnfZqT15cX8cA8i4hz/xPBbn6tDyZ1qfyAbxKAhSVcpS5lQ N3ywIlUrHlPz544pWRby/4byBwAA//8DAFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAATAAAA AAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/WAAAA lAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAGCZRHZGAgAA RwQAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhAFwwi4Ld AAAACwEAAA8AAAAAAAAAAAAAAAAAoAQAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMAAACq BQAAAAA= " stroked="f">
На втором шаге действует команда q3 a→ aПq3, и на машине создается конфигурация
d 7zGc60wj3m8YSpMmo7PxcBxdNQTwOGS19DjpStYZnfbD6WYvMPVCF9HEM6m6N6ap9IG6wFbHm2/z NvZqGIkNvOZQ7JBMC91k4ybiowL7mZIGpzqj7tOGWUGJeqWxIbPBaBTWIAqj8WSIgj3X5OcapjlC ZdRT0j2XPq5OIEvDNTaulJHUx0wOOeO0Rm4OmxXW4VyOVo/7v/gFAAD//wMAUEsDBBQABgAIAAAA IQDN3+rx3wAAAAoBAAAPAAAAZHJzL2Rvd25yZXYueG1sTI9BS8QwEIXvgv8hjOBF3LTNKqU2XWTR g6ALVr2nzdh2bSalye7Wf+940uPwPt77ptwsbhRHnMPgSUO6SkAgtd4O1Gl4f3u8zkGEaMia0RNq +MYAm+r8rDSF9Sd6xWMdO8ElFAqjoY9xKqQMbY/OhJWfkDj79LMzkc+5k3Y2Jy53o8yS5FY6MxAv 9GbCbY/tV31wvPuw5NNH87zdP9VXzT7b0fCSk9aXF8v9HYiIS/yD4Vef1aFip8YfyAYxashuFKtH DWqdgmBAZWsFomEyUSnIqpT/X6h+AAAA//8DAFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAAT AAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/W AAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAONQDE5H AgAARwQAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhAM3f 6vHfAAAACgEAAA8AAAAAAAAAAAAAAAAAoQQAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMA AACtBQAAAAA= " stroked="f">
Tретий шаг обусловлен командой q3 ᴧ →bHq0. В результате чего создается конфигурация:
Эта конфигурация является заключительной, так как машина оказалась в состоянии остановки q0. Таким образом, слово ba переработано в слово ab. Полученную последовательность конфигураций можно записать более коротким способом. Конфигурация записывается в виде следующего слова в алфавите AÈQ: q1ba (содержимое обозреваемой ячейки записано справа от состояния, в котором находится данный момент машина). Вся последовательность записывается так: q1ba ÞL q3a Þ aq LÞ abq0 Пример 2. Применить машину Тьюринга T1 из примера 1 к слову bbabb, исходя из начального положения, при котором в состоянии q1 обозревается крайняя левая ячейка, в котором содержится символ этого слова. Решение
t 8TvXu0a83zCUJm1Br8ajcQzVEMBjkzXSY6cr2RR0mobV915g6pkuo4tnUvVnTFPpA3WBrZ433626 qNXFSZIVlDsk00Lf2TiJeKjBfqSkxa4uqPuwYVZQol5oFORqmGVhDKKRjScjNOz5y+r8hWmOUAX1 lPTHhY+jE8jScIPCVTKSGhTuMznkjN0auTlMVhiHczt6/Zr/+U8AAAD//wMAUEsDBBQABgAIAAAA IQBaqBm43wAAAAoBAAAPAAAAZHJzL2Rvd25yZXYueG1sTI9BT4QwEIXvJv6HZky8GLeAsEGkbMxG Dyauiaj3QkdgpVNCu7v47x1Pepy8L+99U24WO4ojzn5wpCBeRSCQWmcG6hS8vz1e5yB80GT06AgV fKOHTXV+VurCuBO94rEOneAS8oVW0IcwFVL6tker/cpNSJx9utnqwOfcSTPrE5fbUSZRtJZWD8QL vZ5w22P7VR8s7z4s+fTRPG/3T/VVs09eaNjlpNTlxXJ/ByLgEv5g+NVndajYqXEHMl6MCm7SJGVU QbrOQDCQxsktiIbJOMtAVqX8/0L1AwAA//8DAFBLAQItABQABgAIAAAAIQC2gziS/gAAAOEBAAAT AAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAhADj9If/W AAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAhAJfuFGtH AgAARwQAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgAAAAhAFqo GbjfAAAACgEAAA8AAAAAAAAAAAAAAAAAoQQAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAABAAEAPMA AACtBQAAAAA= " stroked="f">
h vVTmtZpeMhcp5Kpld8w2JNaQtZXEmfNqm7XdfdZWi2TZG3LK/vNmeIlTpmE6W1ItHDxqPArUQqrG hqRq3I5UDcNpy7P54rF9K1N3LVPz+oU8etXCrnmxZ738vSgKrcqyLktWu2WZkJZv98ErtZLaJOsf EGzD8ph5y/JYw242ivJYUVQss/etfNUpX4ppUKxWtcCisC6r4ZefVcFtXv7v/QIAAP//AwBQSwME FAAGAAgAAAAhAGnKyAHdAAAABwEAAA8AAABkcnMvZG93bnJldi54bWxMjsFKw0AURfeC/zA8wZ2d pDVRYl5KKeqqCLZC6W6aeU1CM29CZpqkf+90pcvLvZx78uVkWjFQ7xrLCPEsAkFcWt1whfCz+3h6 BeG8Yq1ay4RwJQfL4v4uV5m2I3/TsPWVCBB2mUKove8yKV1Zk1FuZjvi0J1sb5QPsa+k7tUY4KaV 8yhKpVENh4dadbSuqTxvLwbhc1TjahG/D5vzaX097JKv/SYmxMeHafUGwtPk/8Zw0w/qUASno72w dqJFmKdxWCK8JCBCnSxu+YiQPicgi1z+9y9+AQAA//8DAFBLAQItABQABgAIAAAAIQC2gziS/gAA AOEBAAATAAAAAAAAAAAAAAAAAAAAAABbQ29udGVudF9UeXBlc10ueG1sUEsBAi0AFAAGAAgAAAAh ADj9If/WAAAAlAEAAAsAAAAAAAAAAAAAAAAALwEAAF9yZWxzLy5yZWxzUEsBAi0AFAAGAAgAAAAh AMwn+2RsAwAARhgAAA4AAAAAAAAAAAAAAAAALgIAAGRycy9lMm9Eb2MueG1sUEsBAi0AFAAGAAgA AAAhAGnKyAHdAAAABwEAAA8AAAAAAAAAAAAAAAAAxgUAAGRycy9kb3ducmV2LnhtbFBLBQYAAAAA BAAEAPMAAADQBgAAAAA= ">
4.
5.
t 8TvXu0a83zCUJm1OLyfjSQzVEMBjkzXSY6cr2eR0Ngyr773A1HNdRhfPpOrPmKbSB+oCWz1vviu6 qNVkepSkgHKHZFroOxsnEQ812E+UtNjVOXUfN8wKStRLjYJcjtI0jEE00snFGA17/lKcvzDNESqn npL+uPRxdAJZGq5RuEpGUoPCfSaHnLFbIzeHyQrjcG5Hr1/zv/gJAAD//wMAUEsDBBQABgAIAAAA IQBHoMvy4AAAAAoBAAAPAAAAZHJzL2Rvd25yZXYueG1sTI/BToNAEIbvJr7DZky8GLsUoaHI0phG DyZqIrb3hR2Bys4Sdtvi2zue9DSZzJf//6bYzHYQJ5x870jBchGBQGqc6alVsPt4us1A+KDJ6MER KvhGD5vy8qLQuXFnesdTFVrBIeRzraALYcyl9E2HVvuFG5H49ukmqwOvUyvNpM8cbgcZR9FKWt0T N3R6xG2HzVd1tNz7OGfjvn7ZHp6rm/oQv1H/mpFS11fzwz2IgHP4g+FXn9WhZKfaHcl4MSiIs2TN qIJkxZOBuzRNQNRMLtM1yLKQ/18ofwAAAP//AwBQSwECLQAUAAYACAAAACEAtoM4kv4AAADhAQAA EwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAIAAAAIQA4/SH/ 1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8ucmVsc1BLAQItABQABgAIAAAAIQBH8pCN RwIAAEcEAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQBH oMvy4AAAAAoBAAAPAAAAAAAAAAAAAAAAAKEEAABkcnMvZG93bnJldi54bWxQSwUGAAAAAAQABADz AAAArgUAAAAA " stroked="f">
Более короткая запись этой последовательности конфигураций, т. е. процесса работы машины будет: q1bbabb ÞL q3babb ÞL bq3abb ÞL baq3bb ÞL babq3b ÞL babbq3 LÞ babbb.
Таким образом, слово bbabbпереработано машиной в слово babbb.
Пример 3. Задается машина Тьюринга внешним алфавитом A = {a,b,c}, алфавитом внутренних состояний Q = {q0 ,q1,q2,q3} и программой:
q2a ® q3Лa; q3a ® q1Пb; q1a ® q2Лa; q2b ® q2Лa; q3b ® q3Лb; q1b ® q0Пb; q2c ® q2Лc, q3 L® q3Ha;. q3c ® q3П Заметим, что программа этой машины может быть записана в виде сле- дующей таблицы:
Для того чтобы определить по таблице, что будет делать машина, находясь, например, в состоянии q2 и наблюдая в обозреваемой ячейке символb, нужно найти в таблице клетку, находящуюся на пересечении столбца q2 и строки b. В этой клетке записано q2bЛ. Это означает, что на следующем шаге машина останется в прежнем состоянии q2, сохранит содержимое обозреваемой ячейки b и перейдет к обозрению следующей левой ячейки на ленте. Предположим, что в начальной конфигурации головка находится над крайней правой клеткой. Применим эту машину к слову bbcbb. Последовательность конфигураций, возникающих в процессе работы машины (исходная конфигурация –стандартная начальная): bbcbq 1 b Þ bbcq 2 ba Þ bbq 2 cba Þ bq 2 bcba Þ q 2 bbcba Þ q 2 abbcba Þ Þ bq 3 bbcba Þ bbq 3 bcba Þ bbbq 3 cba Þ bbbcq 3 ba Þ bbbcbq 3 a Þ bbbcq 1 ba Þ Þ bbbq 2 caa Þ bbq 2 bca Þ bq 2 bbca Þ q 2 bbbca Þ q 2 abbbca Þ bq 3 bbbca Þ Þ bbq 3 bbca Þ bbbq 3 bca Þ bbbbq 3 ca Þ bbbbcq 3 Þ bbbbq 1 ca Þ bbbbq 0 aa. Нетрудно заметить, что данная МТ реализует операцию сложения: в результате ее работы на ленте записано подряд столько букв b, сколько их было всего записано по обе стороны от буквы c перед началом работы машины. Из приведенных примеров следует, что МТ – это некоторое правило(алгоритм) для преобразования слов алфавита A È Q, т. е. конфигураций. Таким образом, для определения (построения) машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.
Заключение
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен. Машина Тьюринга дает один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы: − насколько общим является понятие машины Тьюринга? − можно ли считать, что способ задания алгоритмов с помощью машины Тьюринга является универсальным? − может ли всякий алгоритм задаваться таким образом? На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы: Если некоторая процедура четко определена и по природе своей механистична, то модно вполне обоснованно предположить, что найдется машина Тьюринга, способная ее выполнить.
Список используемой литературы
1. Плотников А.Д. Дискретная математика: учеб. пособие / А.Д. Плотников. – М.: Новое издание, 2005. – 288 с. 2. Мощенский В.А. Лекции по математической логике: учебное пособие для студ. ун-тов по спец. «Прикладная математика» / В.А. Мощенский. – Минск: Изд-во БГУ, 1973. – 132 с.; ил. 3. Игошин В.И. Математическая логика и теория алгоритмов /В.И. Игошин. – Саратов: Изд-во Сарат. ун-та, 1991. – 256 с. 4. Гаврилов Г.П. Задачи и упражнения по дискретной математике:учебное пособие / Г.П. Гаврилов, А.А. Сапоженко. – 3-е изд., перераб. – М.:Физматлит, 2006. – 416 с. 5. Кузнецов О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский. – 2-е изд., перераб. и доп. – М.: Энергоатомиздат, 1988. – 480 с.
|
