dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 76
Текст из файла (страница 76)
Машина Тьюринга, которая всегда останавливается, представляет собой хорошую модель “алгоритма”. Если алгоритм решения данной проблемы существует, то проблема называется “разрешимой”, поэтому машины6Точнее, удаляется все, что находится после крайней слева группы нулей, возможно, усеченной. — Прим. ред.338Стр. 338ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀТьюринга, которые всегда останавливаются, имеют большое значение во введении втеорию разрешимости (см. главу 9).8.2.7.
Óïðàæíåíèÿ ê ðàçäåëó 8.28.2.1.Укажите конфигурации МТ (рис. 8.9) при обработке следующего входа:а) (∗) 00;б) 000111;в) 00111.8.2.2.(!) Постройте машины Тьюринга для следующих языков:а) (∗) множество цепочек с одинаковыми количествами символов 0 и 1;б) {anbncn | n ≥ 1};в) {wwR | w — произвольная цепочка из символов 0 и 1}.8.2.3.Постройте машину Тьюринга, которая на вход получает натуральное число Nи добавляет к нему 1 в двоичной записи. Точнее, изначально на ленте стоитзнак $, за которым записано N в двоичном виде.
Вначале головка в состоянииq0 обозревает $. Ваша машина должна остановиться с двоичной записью N + 1на ленте, обозревая ее крайний слева символ и находясь в состоянии qf. При*необходимости можно удалить $, например, q0$10011 |− $qf10100 или*q0$11111 |− qf100000:а) укажите переходы вашей МТ и объясните назначение каждого состояния;б) укажите последовательность МО вашей МТ при обработке входа $111.8.2.4.(!∗) В этом упражнении устанавливается эквивалентность вычисления функцийи распознавания языков для машин Тьюринга. Для простоты рассматриваютсятолько функции из множества неотрицательных целых чисел в множество неотрицательных целых чисел, но идеи этой задачи применимы к любым вычислимым функциям.
Рассмотрим два основных определения.• Графиком функции f называется множество всех цепочек вида [x, f(x)], где x —неотрицательное целое число в двоичной записи, а f(x) — значение функции f нааргументе x (также двоичное).• Говорят, что машина Тьюринга вычисляет функцию f, если, начиная с двоичнойзаписи произвольного неотрицательного целого x на ленте, она останавливается(в любом состоянии) с двоичным f(x).С помощью неформальных, но четких конструкций выполните следующее:а) покажите, как по данной МТ, вычисляющей f, построить МТ, которая допускает график f в качестве языка;8.2.
ÌÀØÈÍÀ ÒÜÞÐÈÍÃÀСтр. 339339б) покажите, как по данной МТ, допускающей график f, построить МТ, котораявычисляет f;в) функция называется частичной, если она может быть неопределенной длянекоторых аргументов. Распространяя идеи этого упражнения на частичныефункции, мы не требуем, чтобы МТ, вычисляющая f, останавливалась, еслиее вход x — одно из чисел, для которых f(x) не определена. Работают ли ваши конструкции для пунктов а и б, если функция f частична? Если нет, объясните, как их нужно изменить, чтобы они работали.8.2.5.Рассмотрим машину ТьюрингаM = ({q0, q1, q2, qf}, {0, 1}, {0, 1, B}, δ, q0, B, {qf}).Неформально, но четко опишите язык L(M), если δ состоит из следующего множества правил:а) (∗) δ (q0, 0) = (q1, 1, R); δ(q1, 1) = (q0, 0, R); δ(q1, B) = (qf, B, R);б) δ(q0, 0) = (q1, B, R); δ(q0, 1) = (q1, B, R); δ(q1, 1) = (q1, B, R); δ(q1, B) = (qf, B, R);в) (!) δ(q0, 0) = (q1, 1, R); δ(q1, 1) = (q2, 0, L); δ(q2, 1) = (q0, 1, R);δ(q1, B) = (qf, B, R).8.3.
Òåõíèêà ïðîãðàììèðîâàíèÿ ìàøèí ÒüþðèíãàНаша цель — обосновать, что машину Тьюринга можно использовать для вычислений так же, как и обычный компьютер. В конечном счете, мы хотим убедить вас, что МТравна по своей мощи обычному компьютеру. В частности, она может выполнять некоторые вычисления, имея на входе другие машины Тьюринга, подобно тому, как описаннаяв разделе 8.1.2 программа проверяла другие программы. Именно это свойство “интроспективности” как машин Тьюринга, так и компьютерных программ позволяет доказывать неразрешимость проблем.Для иллюстрации возможностей МТ представим многочисленные приемы интерпретации ленты и конечного управления машины Тьюринга.
Ни один из этих приемов нерасширяет базовую модель МТ; они лишь делают запись более удобной. В дальнейшемони используются для имитации расширенных моделей машин Тьюринга с дополнительными свойствами, например, с несколькими лентами, на базовой модели МТ.8.3.1. Ïàìÿòü â ñîñòîÿíèèКонечное управление можно использовать не только для представления позиции в“программе” машины Тьюринга, но и для хранения конечного объема данных. Рис. 8.13 иллюстрирует этот прием, а также идею многодорожечной ленты. При этом конечное управление содержит не только “управляющее” состояние q но и три элемента данных A, B и C. Данная техника не требует никакого расширения модели МТ; мы просто рассматриваем состоя340Стр.
340ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀние в виде кортежа. На рис. 8.13 состояние имеет вид [q, A, B, C]. Такой подход позволяетописывать переходы более систематично, что зачастую проясняет программу МТ.СостояниеПамятьДорожка 1Дорожка 2Дорожка 3Рис. 8.13. Машина Тьюринга с памятью в конечном управлении и несколькими дорожкамиПример 8.6. Построим МТM = (Q, {0, 1}, {0, 1, B}, δ, [q0, B], B, {[q1, B]}),которая запоминает в своем конечном управлении первый увиденный символ (0 или 1) ипроверяет, не встречается ли он еще где-нибудь во входной цепочке.
Таким образом, Mдопускает язык 01*+10*. Допускание регулярных языков (вроде данного) не сужает возможностей машин Тьюринга, а служит лишь простым примером.Множество состояний Q есть {q0, q1} × {0, 1, B}, т.е. состояния рассматриваются какпары из двух следующих компонентов.1.Управляющая часть (q0 или q1) запоминает, что делает МТ.
Управляющее состояниеq0 сигнализирует о том, что M еще не прочитала свой первый символ, а q1 — чтоуже прочитала, и проверяет, не встречается ли он где-нибудь еще, продвигаясьвправо до достижения пустой клетки.2.В части данных хранится первый увиденный символ (0 или 1). Пробел B в этом компоненте означает, что никакой символ еще не прочитан.Функция переходов δ определена следующим образом.1.δ([q0, B], a) = ([q1, a], a, R) для a = 0 или a = 1. Вначале управляющим состояниемявляется q0, а частью данных — B. Обозреваемый символ копируется во второйкомпонент состояния, и M сдвигается вправо, переходя при этом в управляющее состояние q1.2.δ([q1, a], a ) = ([q1, a], a , R), где a — “дополнение” a, т.е. 0 при a = 1 и 1 при a = 0.В состоянии q1 машина M пропускает каждый символ 0 или 1, который отличаетсяот хранимого в состоянии, и продолжает движение вправо.8.3.
ÒÅÕÍÈÊÀ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀСтр. 3413413.δ([q1, a], B) = ([q1, B], B, R) для a = 0 или a = 1. Достигая первого пробела, M переходит в допускающее состояние [q1, B].Заметим, что M не имеет определения переходов δ([q1, a], B) для a = 0 или a = 1. Таким образом, если M обнаруживает второе появление символа, который был записан в ее памятьконечного управления, она останавливается, не достигнув допускающего состояния. 8.3.2.
Ìíîãîäîðîæå÷íûå ëåíòûЕще один полезный прием состоит в том, чтобы рассматривать ленту МТ как образованную несколькими дорожками. Каждая дорожка может хранить один символ (в одной клетке),и алфавит МТ состоит из кортежей, с одним компонентом для каждой “дорожки”. Например,клетка, обозреваемая ленточной головкой на рис. 8.13, содержит символ [X, Y, Z]. Как и память в конечном управлении, множественные дорожки не расширяют возможностей машинТьюринга. Это просто описание полезной структуры ленточных символов.Пример 8.7. Типичное использование многодорожечных лент состоит в том, что одна дорожка хранит данные, а другая — отметку. Можно отмечать каждый символ, использованный определенным образом, или небольшое число позиций в данных.
Данныйприем фактически применялся в примерах 8.2 и 8.4, хотя лента там и не рассматриваласьявно как многодорожечная. В данном примере вторая дорожка используется явно дляраспознавания следующего языка, который не является контекстно-свободным.Lwcw = {wcw | w принадлежит (0+1)+}Построим машину ТьюрингаM = (Q, Σ, Γ, δ, [q0, B], [B, B], {[q9, B]}),компоненты которой имеют следующий смысл.Q — множество состояний, которое представляет собой {q1, q2, …, q9} × {0, 1, B}, т.е.множество пар, состоящих из управляющего состояния qi и компонента данных 0, 1или B. Вновь используется разрешенное выше запоминание символа в конечномуправлении.Γ — множество ленточных символов {B, *} × {0, 1, c, B}. Первый компонент, т.е.
дорожка, может быть пустым или “отмеченным”, что представлено, соответственно, пробелом или *. Символ * используется для отметки символов первой и второй группиз 0 и 1, в итоге подтверждающей, что цепочки слева и справа от центрального маркера c совпадают. Второй компонент ленточного символа представляет то, чем какбы является сам по себе ленточный символ, т.е. [B, X] рассматривается как ленточный символ X для X = 0, 1, c, B.Σ — входными символами являются [B, 0] и [B, 1], которые, как только что указано, обозначают, соответственно, 0 и 1.δ — функция переходов определена следующими правилами, в которых a и b могут обозначать как 0, так и 1.342Стр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
