close

Вход

Забыли?

вход по аккаунту

?

Универсальный исполнитель

код для вставкиСкачать
§
9
Универсальный
исполнитель
Исполнитель
А
имитирует
В
, если
:
•
Каждому объекту, над которым выполняет действия исполнитель В, однозначно соответствует объект, над которым выполняет действия исполнитель А (
имитация среды исполнителя
)
•
Каждому допустимому действию исполнителя В над тем или иным объектом среды однозначно сопоставимо допустимое действие исполнителя А над соответствующим объектом его среды (
имитация действий
)
•
Каждая инструкция, составленная для исполнителя В, и приводящая при е исполнении к определенному результату может быть преобразована имитацией допустимых действий в инструкцию для исполнителя А, исполнение которой приводит к соответствующему результату в среде исполнителя А.
Универсальный
исполнитель
Машина
Э
. Поста
(1937 г
.)
Абстрактная машина Поста представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V». У машины есть головка, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, либо проверять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка находится над одной из клеток ленты и, как говорят, обозревает ее. Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста. Работа машины Поста заключается в том, что головка передвигается вдоль ленты (на одну клетку за один шаг) влево или вправо, наносит или стирает метки, а также распознает, есть ли метка в клетке в соответствии с заданной программой, состоящей из отдельных команд.
Машина
А
.
Тьюринга
можно считать, что у нас имеется сообщение, записанное в некотором алфавите, и его требуется преобразовать в другое сообщение.
Для обозначения пробела будем использовать ±
а
0
. Остальные символы алфавита, используемого для записи сообщений на ленту, будем обозначать а
1
, а
2
, ..., а
n
. Если, к примеру, нам требуется записать задачу вычисления суммы двух чисел, то алфавит можно взять таким: а
0
; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; ,; +; =.
Машина
Тьюринга
Начальная клетка
Сообщение, записанное на ленте, обрабатывается неким устройством, и результат снова записывается на ленту. Поскольку исполнитель формальный, он не вникает в смысл сообщения, а по составленной для него инструкции заменяет одни символы на другие.
Машина
Тьюринга
Машина Тьюринга формально описывается набором двух алфавитов: А
= {
а
1
, а
2
, ..., а
} и Q
= {
q
0
, q
1
, q
2
, ..., q
m
}. Алфавит А
называется внешним
и служит для записи исходных сообщений, алфавит
Q
называется внутренним
и описывает набор состояний считывающе
-
печатающего
устройства. Допустимые
действия
машины
Тьюринга
записать какой
-
либо символ внешнего алфавита в секцию ленты (символ, бывший там до того, затирается);
сместиться в соседнюю секцию;
сменить состояние на одно из обозначенных символом внутреннего алфавита;
прекратить работу (остановиться).
Вид
команды
:
Вид
команды
фактически
:
a
i
Пq
j
—
в обозреваемую секцию записать a
i
, сместиться вправо (к следующей секции) и перейти в состояние q
j
;
a
i
Лq
j
—
в обозреваемую секцию записать a
i
, сместиться влево и перейти в состояние q
j
;
a
i
Нq
j
—
в обозреваемую секцию записать a
i
, остановиться и перейти в состояние q
j
.
Операционно
-
логический
блок
У этого блока имеется два входа: через один из них поступает информация о том, какой символ стоит в обозреваемой ячейке, через другой ²
информация о том, в каком состоянии находится машина на данном шаге своей работы. Эта информация однозначно определяет, какую именно команду следует выполнить машине. Поскольку команда может содержать указание на выполнение трех действий ²
записи символа на ленту, смещения и смены состояния ²
операционно
-
логический блок имеет три выхода: запись символа A
, смещение M
и смена состояния Q
Функциональная
схема
Внешний алфавит/Состояние
машины
q
0
…
q
j
…
q
m
а
0
а
1
…
а
i
а
i
П
q
j
…
а
m
Например
:
Q
A
q
1
a
0
*
Н
q
0
*
*
Л
q
1
Тезис
Тьюринга
Для задачи существует алгоритм решения тогда и только тогда, когда имеется подходящая машина Тьюринга, посредством которой можно решить эту задачу.
Автор
zukovaivik
Документ
Категория
Презентации
Просмотров
934
Размер файла
511 Кб
Теги
универсальных, исполнителя
1/--страниц
Пожаловаться на содержимое документа