Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
VDM-123.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

Пусть в некоторый момент головка машины обозревает символ , находясь в состоянии , тогда:

  1. Если в клетке команда cDq, то машина заменит в ячейке символ на с, перейдет в состояние q, осуществит движение D и приступит к выполнению следующей команды;

  2. Если в клетке стоит пустая команда, то машина останавливается.

Итак, машина, начиная из исходной ситуации, осуществляет переработку исходной записи на ленте. При этом имеются две возможности:

    1. При работе машины появится пустая команда – машина останавливается и на ленте получается заключительная запись. Состояния, в которых машина останавливается, называются заключительными.

    2. При работе машины пустая команда не появится – машина никогда не остановится.

Введенные нами машины называются машинами Тьюринга.

0

1

1R

Пример. Пусть к = 2, Т:

0

1

1R

Машина, которая в произвольной записи, начиная из любой ячейки, двигаясь вправо, находит первый нуль.

Итак, машина Тьюринга представляет собой (абстрактное) устройство, состоящее из ленты, управляющего устройства и считывающей головки.

Методы построения машин Тьюринга

1. Принцип двойственности для программ (машин).

Пусть Т – любая программа. Обозначим через программу, которую получаем из Т, если в Т заменить в командах R на L, L на R. Программа называется двойственной к T.

Пример.

Т: :

0

1

1R

0

1

1L


Очевидно, что = Т, т.е. понятие двойственности программ является взаимным.

Машины M и M* , соответствующие программам Т и , называются двойственными. Двойственные машины M и M* функционируют симметричным образом.

2. Последовательное подключение одной машины к другой.

Пусть M0 и M1 – две произвольные машины Тьюринга над одним и тем же входным алфавитом {0, 1, …, k-1}, множества состояний которых не пересекаются. Пронумеруем числами 0, 1, …, l-1 все пустые клетки (команды) программы Т0 машины M0. Пусть p(x) – произвольный предикат на множестве {0,1, …, l-1}. Построим машину M, которую и будем называть последовательным подключением машины M1 к M0 (относительно предиката p(x)). Для этого из таблиц Т0 и Т1 машин M0 и M1 построим новую таблицу Т.

… …

’ … ’ … ’

0

Т0’

Т1

…

…

k-1

В ней первая половина совпадает с таблицей Т0 для тех клеток из Т0 , в которых стоит не пустая команда. В тех клетках , ({0,1,…, l -1}), для которых р()=1, в таблице Т стоит команда S ’ (где номер строки, в которой находится эта клетка  ’ - начальное состояние M1). В тех клетках , для которых р()=0, в таблице Т стоит пустая команда. Вторая половина таблицы Т полностью совпадает с таблицей Т1.

Итак, работа машины M состоит в следующем: исходная запись ленты сначала перерабатывается машиной M0, и если машина M0 заканчивает работу по команде такой, что р()=1, то содержимое ленты перерабатывается машиной M1. При этом начальной ячейкой для M1 будет ячейка, в которой остановилась M0. Действительно, машина M в некотором смысле осуществляет последовательную работу машин M0 и M1.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]