Реферат: Алгоритми Маркова

Як алфавіт даних і безлічі станів для МТС візьмемо об'єднання алфавітів даних і безлічі станів для А і В, тобто

DC=DADВ, QC= QAQB

В програмі для А всі правила ap®b! w, де a,bÎDA* wÎ{Л, П, Н} замінимо на ap®bqoBw, де qoBÎ QB - початковий стан для В. Это забезпечить включення У в той момент, коли А свою роботу закінчила і не раніше, оскільки QAQB=Æ.

Що і т.д.

????????? ????? ???????? ??? ? ???????? ?? ??????? 3.3

Рис 3.3. Структура табличного запису програм для Машини З.

Означення. Паралельною композицією Машин Тюрінга А і В назвемо таку Машину З, для якої:

DC=DADB

QC=QAQB

C(a||b) =A(a||b) °B=B(a||b) °A=A(a) ||B(b).

З цього визначення видно, що порядок застосування МТА і МТВ не впливає на результат. Він буде таким же неначебто ми незалежно застосували А до слова a, а В до слова b.

Теорема 3.2 Для будь-яких МТ А і МТ В можна ефективно побудувати МТ З таку, що С=А||В

Обгрунтовування. Ми не даватимемо тут строго доказу з причини його технічної складності. Покажемо лише обгрунтовування правильності затвердження теореми. Позначимо DC=DADB; QC=QAQB.

Основна проблема: як гарантувати щоб А не торкнулася слова b, а В - слово a. Для цього введемо в алфавіт DС символ ||. Додамо для всіх станів qiÎQC таких, що qiÎQA правила вигляду ||qi®||qiЛ, тобто каретка машини А буде, натикаючись на символ ||, йти вліво. Відповідно для всіх qjÎQC таких, що qjÎQB додамо правила вигляду ||qj®||qjП, тобто каретка машини В йтиме управо. Тим самим ми як би обмежуємо стрічку для А справа, а для В зліва.

Істотним тут є питання: чи не виявляться обчислювальні можливості Машини Тюрінга з напівстрічкою слабіше, ніж обчислювальні можливості Машини Тюрінга з повною стрічкою?

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

Теорема 3.3 Для будь-яких Машин Тюрінга А, В і Ф, мають один і той же алфавіт S, може бути ефективно побудований машина З над тим же алфавітом S, така що

Доказ.

Позначимо: E(Р) тотожну машину, тобто Е(Р) =Р

СМІТТЮ(Р) копіюючу машину, тобто СМІТТЮ(Р) =Р||Р

де ||ÏS.

BRANCH(P) - ця машина переходить або в стан р1, або в змозі ро. Її програма складається з 4-х команд:

1qo®1р1П

||р1®||р1П

0qo®0роП

||ро®||роП

Побудуємо машину