Нормальные алгорифмы Маркова

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

Известны случаи построения школьниками железных машин Тьюринга с колесами.

Но машина Тьюринга – это все-таки прежде всего метод математического моделирования.

Машина Тьюринга включает:

1. Потенциально бесконечную (вправо) ленту, разделенную на ячейки.

2. Считывающе-записывающую головку с устройством управления (УУ).

3. Алфавит внутренних состояний {q_0, q₁...q_n}.

4. Входной-выходной алфавит.

Определяется начальная конфигурация. Головка смотрит на какую-то ячейку и устройство управления находится в начальном состоянии q₁.

Устройство управления на основании считанного из ячейки символа и внутреннего состояния пишет в ячейку символ (возможно, тот же самый), совершает действие D и переходит в новое внутреннее состояние (возможно прежнее). Это и есть команда Машины Тьюринга, которую можно записать так:

a_iq_i ® a_jD_jq_j.

D = {Л, П, С} - множество действий.

Л – влево, П – вправо, С - стоять.

Совокупность команд составляет программу машины Тьюринга, которая обычно оформляется в виде таблицы.

Машина заканчивает работу, когда переходит в состояние q_0.

l - пустой символ.

Пример: Построим машину Т, которая в сплошной последовательности 1 стирает первую и две последние. (l - пустой символ).

Автор - А.А. Марков, отдавал предпочтение транскрипции алгорифм. Нормальные алгорифмы Маркова представляются нормальной схемой подстановок, которая состоит из совокупности подстановок, расположенных в определенном порядке. Подстановки имеют вид: P ® (·)Q(P ® Q –(простая)подстановка, P ® ·Q –заключительная подстановка).

Говорят, что строка R входит в строку L, если L имеет вид L₁RL₂.

Говорят, что подстановка применима к слову, если строка, соответствующая левой части подстановки, входит в слово. Применение заключается в замене в преобразуемом слове левой строки подстановки правой.

Две особые подстановки:

P ® - аннулирующая.

® Q - порождающая.

Механизм работы нормальных алгорифмов:

0) Дано (преобразуемое) слово – цепочка символов фиксированного алфавита и нормальная схема подстановок, содержащая фиксированную последовательность простых и заключительных подстановок.

1) Слово всегда просматривается слева направо.

Схема подстановок просматривается всегда начиная с первой подстановки и, если подстановку можно применить, то она применяется к самому левому вхождению этой строки в преобразуемое слово.

2) Работа алгоритма заканчивается тогда, когда ни одна из подстановок не применима, либо.использована заключительная подстановка.

Примеры.