Реферат: Нормальные Алгоритмы Маркова Построение алгоритмов из алгоритмов

Основная проблема: как гарантировать чтобы А не затронула слово b , а В - словоa . Для этого введем в алфавит D_С символ ||. Добавим для всех состояний q_i ÎQ_C таких, что q_i ÎQ_A правила вида ||q_i ®||q_i Л, т.е. каретка машины А будет, натыкаясь на символ ||, уходить влево. Соответственно для всех q_j ÎQ_C таких, что q_j ÎQ_B добавим правила вида ||q_j ®||q_j П, т.е. каретка машины В будет уходить вправо. Тем самым мы как бы ограничиваем ленту для А справа, а для В слева.

Существенным здесь является вопрос: не окажутся ли вычислительные возможности Машины Тьюринга с полулентой слабее, чем вычислительные возможности Машины Тьюринга с полной лентой?

Оказывается справедливо следующее утверждение: множество алгоритмов, реализуемых МТ с полулентой, эквивалентно множеству алгоритмов, реализуемых МТ с полной лентой. Обозначим Ф(Р) Машину Тьюринга, реализующую распознающий алгоритм:

Теорема 3.3. Для любых Машин Тьюринга А, В и Ф, имеющих один и тот же алфавит S, может быть эффективно построена машина С над тем же алфавитом S, такая что

Доказательство.

Обозначим: E(Р) тождественную машину, т.е. Е(Р)=Р

СOPY(Р) копирующую машину, т.е. СOPY(Р)=Р||Р,

где ||ÏS.

BRANCH(P) - эта машина переходит либо в состояние р₁ , либо в состоянии р_о . Ее программа состоит из 4-х команд:

1q_o ®1р₁ П

||р₁ ®||р₁ П

0q_o ®0р_о П

||р_о ®||р_о П

Построим машину

Эта машина строится по следующей формуле:

Согласно теоремам 3.1 и 3.2., мы можем построить машину , зная Е, Ф и COPY. Теперь, имея , BRNCH, A и В, можно построить машину С следующим образом:

Машина oBRANCH заканчивает свою работу либо в состоянии р₁ , если слово P обладает нужным свойством, либо в состоянии р_о , находясь в начале слова P. Поэтому, если принять у машины А состояние р₁ , как начальное, а у машины В состояние р_о , как начальное, то машина А будет включена при условии, что Ф(Р)=1, а машина В будет включена, если Ф(Р)=0.

Правило композиции, определяемое этой теоремой будем записывать, если Ф то А иначе В.

Теорема 3.4. Для любых машин А и Ф можно эффективно построить машину L такую, что

L(P)={ Пока Ф(Р)=1, применяй А }

Доказательство: Заменим в доказательстве теоремы 3.3. машину В машиной Е, а заключительное состояние в машине В заменим на начальное состояние в машине . В итоге получим нужный результат.

Теорема 3.5. (Бомм, Джакопини, 1962)

Любая Машина Тьюринга может быть построена с помощью операции композиций o, || , если Ф, то А иначе В, пока Ф применяй А.

Эту теорему мы даем здесь без доказательства.

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