Машины Тьюринга

1.

МАШИНЫ ТЬЮРИНГА

2.

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

3.

• Описывая различные алгоритмы для МТ и
доказывая реализуемость всевозможных
композиций алгоритмов, Тьюринг показал
разнообразие возможностей предложенной им
конструкции, что позволило ему выступить с
тезисом: «Всякий алгоритм может быть
реализован соответствующей машиной
Тьюринга». Доказать тезис нельзя, так как в его
формулировке не определено понятие «всякий
алгоритм». Его можно только обосновывать,
представляя различные алгоритмы в виде МТ.

4.

Неформальное определение машины
Тьюринга
• Машина Тьюринга — это автомат, имеющий
бесконечную в обе стороны ленту, считывающую
головку и управляющее устройство. Управляющее
устройство может находиться в одном из состояний,
образующих конечное множество Q={q0, q1,..., qn}Множество Q называют внутренним алфавитом машины
Тьюринга. Среди состояний управляющего устройства
выделяются начальное состояние q0, из которого
автомат начинает свою работу, и заключительное
состояние qz, в котором автомат завершает работу.

5.

• Принципиальное отличие МТ от вычислительных
машин состоит в том, что её запоминающее
устройство представляет собой бесконечную
ленту. Лента разделена на ячейки, в каждую из
которых может быть записан один символ из
входного алфавита машины Тьюринга А={а0, а1 ...,
аn,}. В алфавите А выделяют два символа
специального назначения: а0 — символ для
обозначения пустой ячейки, a1 — символ, который
используется для разделения цепочек на ленте.
Во время функционирования МТ заполнено
конечное число ячеек.

6.

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

7.

Формальное описание машины Тьюринга
• Машиной Тьюринга называется упорядоченная семерка
вида;
• Т = (Q, А, δ, р0, рz, а0, а1), где
• Q - конечное множество состояний управляющего
устройства;
• А - входной алфавит;
• δ — функция переходов, или отображение δ: Q * А —> Q
* А * S, где S = {R, L, Е} - направления сдвига
считывающей головки;
• р0 - начальное состояние, р0 ϵ Q; pz - заключительное
состояние, pz ϵ Q; а0 - символ для обозначения пустой
ячейки, а0 ϵ А; а1 - символ, который используется для
разделения цепочек на ленте, а1 ϵ А.

8.

• Командой машины Тьюринга является элемент функции
переходов, которая, например, может иметь вид: qa—
>pbR, где
• q ϵ Q - состояние машины Тьюринга до выполнения
команды,
• р ϵ Q - состояние, в которое переходит машина Тьюринга
после выполнения команды,
• а ϵ А - символ, читаемый автоматом со входной ленты
• b ϵ A - символ, который может быть записан в ячейку в
результате выполнения команды
• R ϵ S - сдвиг считывающей головки вправо на одну
ячейку

9.

Понятие конфигурации машины Тьюринга
• Конфигурация МТ представляется следующим образом:
• t = <CqaB>, где
• С - цепочка на ленте слева от считывающей головки;
• q - состояние МТ;
• а - символ, читаемый автоматом со входной ленты;
• В - цепочка на ленте справа от считывающей головки.
• Конфигурация t=<CqaB> непосредственно переходит в
конфигурацию t1=<C1q1a1B1>, если t1 получена в результате
применения одной команды к исходной конфигурации, т.е. t—>t1.

10.

• Конфигурация, содержащая состояние р0, называется
начальной, а содержащая состояние рz заключительной. Если цепочка С в конфигурациях
пустая, то начальная и заключительная конфигурации
называются стандартными.
• Машина Тьюринга перерабатывает цепочку х в цепочку
у, если, действуя из начальной конфигурации и имея на
ленте цепочку х, она переходит в заключительную
конфигурацию, имея на ленте цепочку у. Если начальная
и заключительная конфигурации являются
стандартными, то процесс переработки цепочки х в
цепочку у называется правильной переработкой.

11.

Способы представления машины Тьюринга
• Машина Тьюринга может быть представлена
совокупностью команд, графом и таблицей
соответствия.
• Представление МТ совокупностью команд. МТ считается
заданной, если заданы её внешний и внутренний
алфавиты, функция переходов в виде
последовательности команд, начальная конфигурация,
заключительное состояние и указано, какой символ
алфавита обозначает пустую ячейку. Чтобы записать
совокупность команд, нужно воспользоваться
следующими правилами:

12.

1. начальному шагу алгоритма
ставится в соответствие начальное
состояние р0;
2. соседним шагам алгоритма
соответствует переход в смежные
состояния;
3. последний шаг алгоритма вызывает
переход в заключительное
состояние.

13.

• Пример. Построить машину Тьюринга, которая
инвертирует входную цепочку, записанную в
двоичной системе счисления.
• Решение. В соответствии с условием задачи
входной алфавит МТ определим как множество
А={0, 1, ɛ}, где символ ε соответствует пустой
ячейке. Внутренний алфавит включает начальное
q0 и заключительное qz состояния управляющего
устройства. Другие элементы множества Q
определим в ходе решения задачи.

14.

•Пусть на ленте записана цепочка х=110011.
Стандартная начальная конфигурация, из
которой МТ начинает работу, имеет вид
q0=110011, где 1 - символ, обозреваемый
считывающей головкой, а стандартная
заключительная конфигурация, в которую
перейдет МТ после завершения операции
инвертирования, должна иметь вид
qz=001100. Реализовать алгоритм
инвертирования входной цепочки позволяет
следующая последовательность команд:

15.

•q0 1 q0 0R,
•q0 0 q0 1R,
•q0 ɛ q1 ɛL,
•q1 0 q1 0L,
•q1 1 q1 1L,
•q1 ɛ qz ɛR.
На первом такте автомат считывает первый слева
символ цепочки, управляющее устройство
находится в начальном состоянии. Затем МТ, не
меняя своего состояния, заменяет символ 1 на 0 или
0 на 1 и сдвигается вправо на один символ. После
просмотра всей цепочки под считывающей
головкой оказывается символ ɛ

16.

• Тогда МТ переходит в новое состояние q1 и
сдвигается влево на один символ. На последующих
тактах управляющее устройство не меняет своего
состояния, оставляет без изменения читаемый
символ и перемещается влево до тех пор, пока не
встретит пустую ячейку. Затем выполняется
последняя команда, которая управляющее
устройство переводит в заключительное состояние,
считывающую головку смещает вправо на один
символ, и МТ переходит в стандартную
заключительную конфигурацию. Внутренний
алфавит q включает три состояния: Q={ q0, q1, qz}

17.

•Таким образом, МТ выполнила переработку
цепочки х в цепочку у. Действуя из начальной
конфигурации и имея на ленте цепочку х, МТ
перешла в заключительную конфигурацию,
имея на ленте цепочку у. Начальная и
заключительная конфигурации стандартные,
поэтому процесс переработки цепочки х в
цепочку у является правильной
переработкой.

18.

Представление МТ графом
• При представлении МТ в виде графа каждому
состоянию ставится в соответствие вершина графа,
а каждой команде - помеченная дуга. Каждая дуга
помечается командой, в которой не записывается
состояние МТ. Запись команды можно сократить,
если опускать в правой части команды
неизменяющиеся символы, например: запись
• 1—>1L эквивалентна записи 1—>L.

19.

Пример
• Дуги графа помечены двумя способами:
• а) 1—>0L или 0—>1L;
• б) 1—>L, что равнозначно 1—>1L, или ɛ—>R, что равнозначно ɛ-- >
ɛR

20.

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

21.

Пример
• Заключительное состояние qz в таблицу не включается, так как
из этого состояния машина Тьюринга не выполняет никаких
команд.

22.

Машина Тьюринга и вычислимые функции
• Теорема. Машина Тьюринга вычисляет функцию f(x1 х2,...,
Хn), если выполняются следующие условия:
1. для любых х1 х2, ..., хn, принадлежащих области
определения функции, машина Тьюринга из начальной
конфигурации, имея на ленте представление
аргументов, переходит в заключительную
конфигурацию, имея на ленте результат
(представление функции);
2. для любых х1 х2, ..., хn, не принадлежащих области
определения функции, машина Тьюринга из начальной
конфигурации работает бесконечно.

23.

• Если начальная и заключительная конфигурации
машины Тьюринга являются стандартными, то говорят,
что машина Тьюринга правильно вычисляет функцию f.
• Функция называется вычислимой по Тьюрингу, если
существует машина Тьюринга, вычисляющая её.
• Для того, чтобы доказать вычислимость функции, а в
дальнейшем и существование алгоритма, необходимо
построить машину Тьюринга, реализация которой на
практике зачастую представляет собой трудоемкую
задачу.

24.

• В связи с этим возникает необходимость
разбиения алгоритма на отдельные задачи,
каждая из которых будет решаться отдельной
машиной Тьюринга. Если объединить программы
этих машин, то получится новая программа,
позволяющая решить исходную задачу.
• Машины Тьюринга могут вычислять искомую
функцию с восстановлением и без
восстановления. Вычисление функции с
восстановлением означает работу машины
Тьюринга с сохранением исходных данных на
ленте:

25.

• р0 1х1*...* 1xn=>pz 1 f(x1,x2,…xn)#1x1*…*1xn
• Приведенное определение позволяет получить на ленте
сначала результат, а затем исходные данные. В отдельных
случаях результат можно поместить после исходных данных:
• P0 1 x1*…*1xn=>pz1x1*…*1xn#1 f(x1, x2,…,xn)
• где # - символ-разделитель цепочек на ленте.
• Вычисление функции без восстановления означает работу
машины Тьюринга без сохранения исходных данных:
• P0 1x1 *…* 1xn => pz1 f(x1, x2, …xn)
• Справедливо утверждение, что всякая правильно
вычислимая функция правильно вычислима с
восстановлением.

26.

Операции над машинами Тьюринга
• Композиция. Пусть машины T1 и Т2 имеют программы P1 и
Р2. Предположим, что внутренние алфавиты этих машин
не пересекаются; пусть qz1 - заключительное состояние
машины Т1 a q02 - начальное состояние машины Т2.
Заменим всюду в программе P1 заключительное
состояние qz1 на начальное состояние q02 машины Т2 и
полученную программу объединим с программой Р2.
Новая программа Р определяет машину Тьюринга Т,
называемую композицией машин T1 и Т2 по паре
состояний (qz1, q02). Композиция машин может быть
обозначена Т1 • Т2 или T1T2.

27.

• Операция композиции, выполняемая над алгоритмами,
позволяет получать новые, более сложные, алгоритмы,
сконструированные на основе известных и более простых
алгоритмов.
• Итерация. Эта операция применима только к одной машине.
• Пусть qz - заключительное состояние машины Т, a qn - какое-либо
состояние машины Т, не являющееся заключительным. Заменим
всюду в программе Р машины Т состояние qz на qn. Полученная
программа определяет новую машину T’(qz, qn), которая
называется итерацией машины Т по паре состояний (qz, qn). Если
МТ имеет одно заключительное состояние, то после выполнения
итерации получается машина, не имеющая заключительного
состояния.

28.

• Разветвление. Пусть МТ Т1 Т2 и Т3 задаются
программами Р1 Р2 и Р3 соответственно. Считаем, что
внутренние алфавиты этих машин попарно не
пересекаются. Пусть qz11 и qz21 - какие- либо различные
заключительные состояния машины Т1. Заменим всюду в
программе Р1 состояние qz11 начальным состоянием q02
машины Т2, а состояние qz21 начальным состоянием q03
машины Т3. Затем новую программу объединим с
программами P1 и Р2. Получим программу Р, задающую
МТ и обозначаемую:
• Т = T(T1, (qz11, q02), Т2, (qz21, q03),Т3).
• Машина Т называется разветвлением машин Т2 и Т3,
управляемых машиной Т1.