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

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

Построение алгоритмов из алгоритмов.

До сих пор, строя ту или иную МТ, или НАМ мы каждый раз все делали заново. Естественно задать вопрос, а нельзя ли при построении, например, новой МТ пользоваться уже построенной ранее МТ.

Например, МТ₃ из примера 3

U₃ ((n)₁ )=(n)₁₀

по существу есть надлежащим образом объединенные МТ для U₁ (n)=n+1 и U₂ ((n)₁ )=(n-1)₁ .

Аналогичный вопрос можно сформулировать для НАМ. Другими словами можно ли аккумулировать знания в форме алгоритмов так, чтобы из них можно было строить другие алгоритмы.

Мы рассмотрим эту проблему применительно к МТ. Однако все сформулированные нами утверждения будут справедливы и для НАМ и для других эквивалентных уточнений понятия алгоритма. Эквивалентость уточнений понятия алгоритма мы рассмотрим позже.

Определение.3.2. Будем говорить, что МТ₁ можно эффективно построить из МТ₂ и МТ₃ если существует алгоритм, который позволяет, имея программу для МТ₂ и МТ₃ , построить программу для МТ₃ .

Определение.3.3.Последовательной композицией МТ А и В называется такая МТ С, что

область применимости МТ А и С совпадают;

C(a)=B(A(a)).

Другими словами, применение С к слову a дает такой же результат, как последовательное применение к этому же слову сначала А, а потом к результату применения А - В.

Последовательную композицию МТ_А и МТ_В будем обозначать АoВ.

Теорема 3.1. Пусть даны МТ А и В, такие, что В применима к результатам работы А и Q_A Q_B =Æ.

Тогда можно эффективно построить МТ С такую, что С= АoВ.

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

В качестве алфавита данных и множества состояний для МТ_С возьмем объединение алфавитов данных и множеств состояний для А и В, т.е.

D_C =D_A D_В , Q_C = Q_A Q_B

В программе для А все правила ap®b!w, где a,bÎD_A *, wÎ{Л, П, Н} заменим на ap®bq_o ^B w, где q_o ^B ÎQ_B - начальное состояние для В. Это обеспечит включение В в тот момент, когда А свою работу закончила и не раньше, т.к. Q_A Q_B =Æ.

Что и т.д.

Табличная запись программы для С показана на рисунке 3.3.

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

Определение3.4.Параллельной композицией Машин Тьюринга А и В назовем такую Машину С, для которой:

D_C =D_A D_B

Q_C =Q_A Q_B

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

Из этого определения видно, что порядок применения МТ_А и МТ_В не влияет на результат. Он будет такой же как если бы мы независимо применили А к слову a, а В к слову b.

Теорема 3.2 Для любых МТ А и МТ В можно эффективно построить МТ С такую, что С=А||В