Содержание
- 2. § 6.1. Неформальное и формальное описания В этой главе мы рассмотрим еще один тип распознающих устройств
- 3. Было предложено много других формализаций процедуры, и было показано, что все они эквивалентны формализации машины Тьюринга.
- 4. Основная модель (см. рис. 6.1) имеет конечное управление, ленту, которая раз-делена на ячейки, и головку ленты,
- 5. Каждая ячейка может содержать ровно один из конечного числа символов ленты. Первоначально n крайних левых ячеек
- 6. q0∈Q Конечное управление δ: Q × Γ → Q × (Γ \ {B}) × {L, R}
- 7. В один такт, зависящий от символа, сканируемого головкой ленты, и состояния конечного управления, машина Тьюринга 1)
- 8. Определение 6.1. Машина Тьюринга (Tm) является формальной системой: T = (Q, Σ, Γ, δ, q0, F),
- 9. Заметим, что если головка ленты покидает ячейку, она должна напечатать непустой символ в этой ячейке, так
- 10. Мы не позволили Tm печатать пробел ради простоты определения конфигураций. Однако, Tm могла бы иметь другой
- 17. Два других случая, когда Tm останавливается, однако, не принимая: когда значение δ(q, X) при некоторых q∈Q
- 18. Пример 6.1. Построим Tm, распоз-нающую cfl L = {0n1n | n ≥ 1}. Положим T =
- 19. 2. а) δ(q1, 0) = (q1, 0, R); б) δ(q1, Y) = (q1, Y, R); в)
- 20. 3. а) δ(q2, Y) = (q2, Y, L); б) δ(q2, X) = (q3, X, R); в)
- 21. 4. а) δ(q4, 0) = (q4, 0, L) б) δ(q4, X) = (q0, X, R). Машина
- 22. 5. а) δ(q3, Y) = (q3, Y, R) б) δ(q3, B) = (q5, Y, R). Машина
- 23. 6. Во всех случаях, кроме 1–5, функция δ не определена. Рассмотрим действия машины Тьюринга на входной
- 24. Таблица 6.1
- 25. § 6.2. Методы построения машин Тьюринга Машина Тьюринга может “програм-мироваться” во многом так же, как программируются
- 26. § 6.3. Машина Тьюринга как процедура До сих пор мы определяли машину Тьюринга как распознающее устройство.
- 27. Машина Тьюринга в примере 6.1 используется как распознаватель. Заметим, что на некоторых входных цепочках, эта машина
- 28. Следует подчеркнуть, что существуют языки, которые принимаются машинами Тьюринга, не останавливающимися для некоторых цепочек, не содержащихся
- 29. Когда машина Тьюринга рассматри-вается как процедура и оказывается, что она останавливается для всех входных цепочек, то
- 30. Есть процедуры, для которых не существует никакого соответствующего алгоритма. Примером является процедура для определения, порождает ли
- 31. К каждой цепочке эта машина Тьюринга применяет алгоритм, данный в гл. 2, чтобы увидеть, порождается ли
- 32. Имеет место факт, что не существует машины Тьюринга, которая останавли-вается на всех входных цепочках и определяет
- 33. § 6.4. Модификации машин Тьюринга Одна из причин, по которой машины Тьюринга принимаются в качестве общей
- 34. 6.4.1. Машина Тьюринга с бесконечной лентой в обе стороны Теорема 6.1. Если язык L распознается машиной
- 35. 6.4.2. Многоленточная машина Тьюринга состоит из конечного управления с k ленточными головками, по одной на каждой
- 36. При одном движении, зависящем от состояния конечного управления и сканируемого символа каждой из ленточных головок, машина
- 37. Теорема 6.2. Если язык L принимается многоленточной машиной Тьюринга, то он принимается одноленточной машиной Тьюринга.
- 38. 6.4.3. Недетерминированная машина Тьюринга есть устройство с конечным управлением и одной бесконечной в обе стороны лентой.
- 39. Теорема 6.3. Если язык L принимается недетерминированной машиной Тьюринга T1, то он принимается некоторой детерми-нированной машиной
- 40. Тогда любая последовательность вариан-тов движений конечной длины может быть представлена последовательностью цифр от 1 до r.
- 41. Можно построить детерминированную машину Тьюринга T2, моделирующую машину T1. Снабдим её тремя лентами. Лента 1 будет
- 42. Для каждой последовательности цифр, сгенерированной на ленте 2, машина T2 копирует вход на ленту 3 и
- 43. Если машина T1 входит в принимающее состояние, то машина T2 также принимает. Если имеется последовательность вариантов,
- 45. Скачать презентацию