Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 76
Текст из файла (страница 76)
8.2.5. Язык машины Тьюринга Способ допускания языка машиной Тьюринга уже описан интуитивно. Входная цепочка помещается на ленту, и головка машины начинает работу иа крайнем слева символе. Если МТ в конце концов достигает допускающего состояния, то вход допускается, в противном случае — нет, Более формально, пусть М = Я, Х„Г, 4 оь В, Е'! — машина Тьюринга, Тогда ЦМ! представляет собой множество цепочек н из Х, для которых ови !- а!оф при некотором состоянии и из Р и произвольных ленточных цепочках а н В. Это определение было принято при обсуждении машины Тьюринга в примере 8.2, допускавшей цепочки вида О" 1".
Языки, допустимые с помощью машин Тьюринга, часто называются рекурсивно леречислимыми, или РП-языками. Термин "рекурсивно перечислимые" происходит от вы- 8.2. МАШИНА ТЬЮРИНГА 337 числительных формализмов, предшествовавших машинам Тьюринга, но определявших тот же класс языков нли арифметических функций.
Обсуждение источников этого термина представлено во врезке в разделе 9.2.1. Соглашения ио обозначениям машин Тьюринга Обычно для машин Тьюринга используются такие же символы, как и для других ви- дов автоматов, 1. Строчные буквы из начала алфавита обозначают входные символы. 2. Прописные буквы, обычно из конца алфавита, используются для ленточных символов, которые иногда могут быть н входными. Однако для пробела всегда используется В. 3.
Строчные буквы из конца алфавита обозначают цепочки входных символов. 4. Греческие буквы используются для цепочек ленточных символов. 5. Буквы р, д и другие около них в алфавите обозначают состояния. 8.2.6. Машины Тьюринга и останов Существует еще одно понятие "допустимости" для машин Тьюринга — допустимость по астапову.
Говорят, что машина Тьюринга аслганавливается, если попадает в состояние а, обозревая ленточный символ Х, и в этом положении нет переходов, т.е. 4д, Х) не определено. Пример 8.5. Машина Тьюринга лз из примера 8.4 была построена для того, чтобы допускать язык; она не рассматривалась с точки зрения вычисления функции. Заметим, однако, что Мостанавяивается на всех цепочках из символов О и 1, поскольку независимо от входной цепочки машина М в конце концов удаляет вторую группу нулей, если может ее найти, достигает состояния дб н останавливается. СЗ Всегда можно предполагать, что МТ останавливается, если допускает.
Таким образом, без изменения допускаемого языка можно сделать бдд, Х) неопределенной, если д— допускающее состояние. Итак, ° предполагается, что МТ всегда останавливается в допускающем состоянии. К сожалению, не всегда можно потребовать, чтобы МТ останавливалась, если не допускает. Язык машины Тьюринга, которая в конце концов останавливается независимо от того, допускает она нли нет, называется рекурсивным, и его важные свойства будут рассматриваться, начиная с раздела 9.2.1. Машина Тьюринга, которая всегда останавливается, представляет собой хорошую модель "алгоритма".
Если алгоритм решения данной проблемы существует, то проблема называется "разрешимой", поэтому машины б Точнее, удаляется все, что находится после крайней слева группы нулей, возможно, усеченной. — Прим. реа ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 338 Тьюринга, которые всегда останавливаются, имеют большое значение во введении в теорию разрешимости (см. главу 9). 8.2.7. Упражнения к разделу 8.2 8.2.1.
Укажите конфигурации МТ (рис. 8.9) при обработке следующего входа: а) (в) 00; б) 000111; в) 00111. 8.2.2. (!) Постройте машины Тьюринга для следующих языков: а) (*) множество цепочек с одинаковыми количествами символов 0 и 1; б) ( а"Ь"с" ~ л > 1); в) (жн к ! ж — произвольная цепочка из символов 0 и ! ). 8.2.3. Постройте машину Тьюринга, которая на вход получает натуральное число Ф и добавляет к нему ! в двоичной записи. Точнее, изначально на ленте стоит знак $, за которым записано Ф в двоичном виде. Вначале головка в состоянии д, обозревает $. Ваша машина должна остановиться с двоичной записью Ж + 1 на ленте, обозревая ее крайний слева символ и находясь в состоянии о.
При необходимости можно удалить $, например, дв$10011 !- $9210100 или 9,$11111 )- д,100000: а) укажите переходы вашей МТ и объясните назначение каждого состояния; б) укажите последовательность МО вашей МТ при обработке входа $111. 8.2.4. (1в) В этом упражнении устанавливается эквивалентность вычисления функций и распознавания языков для машин Тьюринга. Для простоты рассматриваются только функции из множества неотрицательных целых чисел в множество неотрицательных целых чисел, но идеи этой задачи применимы к любым вычислимым функциям.
Рассмотрим два основных определения. ° Графиком функции Г называется множество всех цепочек вида (х, !(х)), где х— неотрицательное целое число в двоичной записи, а)(х) — значение функции/ на аргументе х (также двоичное). ° Говорят, что машина Тьюринга вычисляет функцию 1, если, начиная с двоичной записи произвольного неотрицательного целого х на ленте, она останавливается (в любом состоянии) с двоичнымЯх). С помощью неформальных, но четких конструкций выполните следующее; а) покажите, как по данной МТ, вычисляющей !; построить МТ, которая допускает график Гв качестве языка; 3.2.
МАШИНА ТЬЮРИНГА 339 б) покажите, как по данной МТ, допускающей график~ построить МТ, которая вьсчисляет); в) функция называется чистичноя, если она может быть неопределенной для некоторых аргументов. Распространяя идеи этого упражнения на частичные функции, мы не требуем, чтобы МТ, вычисляющая 1. останавливалась, если ее вход х — одно из чисел, для которыхЯх) не определена. Работают ли ваши конструкции для пунктов а и б, если функция г" частична? Если нет, обьясните, как их нужно изменить, чтобы они работали. 8.2.5. Рассмотрим машину Тьюринга М=Нд,, )и ),,дс), 10,1), 10,1, В),6,0,,В,1~,)).
Неформально, но четко опишите язык ЦЩ если 6 состоит из следующего множества правил; а) (о) 60)о, О) = (с)с, 1, сс); Щс, 1) = (до, О, й); сз1с)ъ В) = (с1о В, Я); б) фс)о, О) = (дс, В, В); ф уо, 1) = (с)ъ В, Я); фс)с, 1) = (с)„В, Л); исус, В) = ~ср В, Я); в) (с) сХЧо О) = (Чс 1. В)' сХЧс 1) = (с)ь О, С) Щь 1) = (с)о 1, и); адьВ) =1д,В,В). 8.3. Техника программирования машин Тьюринга Наша цель — обосновать, что машину Тьюринга можно использовать для вычислений так же, как и обычный компьютер. В конечном счете, мы хотим убедить вас, что МТ равна по своей мощи обычному компьютеру. В частности, она может выполнять некоторые вычисления, имея на входе другие машины Тьюринга, подобно тому, как описанная в разделе 8.1.2 программа проверяла другие программы. Именно это свойство "интроспективности" как машин Тьюринга, так и компьютерных программ позволяет доказывать неразрешимость проблем.
Для иллюстрации возможностей МТ представим многочисленные приемы интерпретации ленты и конечного управления машины Тьюринга. Ни один из этих приемов не расширяет базовую модель МТ; они лишь делают запись более удобной. В дальнейшем они используются для имитации расширенных моделей машин Тьюринга с дополнительными свойствами, например, с несколькими лентами, на базовой модели МТ. 8.3.1. Память в состоянии Конечное управление можно использовать не только для представления позиции в "программе" машины Тьюринга, но и для хранения конечного объема данных. Рнс.
8.13 иллюстрирует этот прием, а также идею многодорожечной ленты. При этом конечное управление содержит не только "управляющее" состояние с) но и три элемента данных А, В и С. Данная техника не требует никакого расширения модели МТ; мы просто рассматриваем состоя- 340 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА аие в виде кортежа. На рис. 8.13 состояние имеет внд [Ф А, В, С~. Такой подход позволяет описывать переходы более систематично, что зачастую проясняет программу МТ.
Дорожка ! Дорожка 2 Дорсжеа 3 Рис. 8.!3. Машина Тьюринга с аамятью в конечном управлении и несколькими дорожками Пример 8.6. Построим МТ которая запоминает в своем конечном управлении первый увиденный символ [О нли 1) и проверяет, не встречается ли он еще где-нибудь во входной цепочке. Таким образом, М допускает язык 01 +10 . Допускание регулярных языков [вроде данного) не сужает возможностей машин Тьюринга, а служит лишь простым примером.
Множество состояний Д есть [е)„е),] х [О, 1, В), т.е. состояния рассматриваются как пары из двух следующих компонентов. !. Управляющая часть (е)в или е2е) запоминает, что делает МТ. Управляющее состояние йе сигнализиРУет о том, что М еще не пРочитала свой пеРвый символ, а 8, — что умсе а]зачигиала, и проверяет, не встречается ли он где-нибудь еще, продвигаясь вправо до достижения пустой клетки. 2. В части данных хранится первый увиденный символ [О нли 1).
Пробел В в этом ком- поненте означает, что никакой символ еще не прочитан. Функция переходов 6 определена следующим образом. к[с!в, и], а) = [[е)ь а], а, Л) для а= О нли а = 1. Вначале управляющим состоянием является ав, а частью данных — В. Обозреваемый символ копируется во второй компонент состояния, и М сдвигается вправо, переходя при этом в управляющее со- стоЯние йь 2 4[дна], а)= [[чупа], а, Р), где а — "дополнение" а, т.е. О при а=! и! при а=О.
В состоянии е1~ машина М пропускает каждый символ О или 1, который отличается от хранимого в состоянии, и продолжает движение вправо. 8 8. ТЕХНИКА ПРОГРАММИРОВАНИЯ МАШИН ТЬЮРИНГА 341 3. ®сул а], В) = ([дл В), В, й) для а = О или а = 1. Достигая первого пробела, М переходит в допускающее состояние [Вь В]. Заметим, что М не имеет определения переходов ф(с)ь а], В) для а = О или а = 1. Таким образом, если М обнаруживает второе появление символа, который был записан в ее память конечного управления, она останавливается, не достигнув допускающего состояния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
