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

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

Если алфавит А входит во множество В, но АВ, то говорят, что В – расширение алфавита А.

Пусть RA и существует некоторое PR, в этом случае говорят, что Р – это вхождение подстроки в высказывание R.

Марковская подстановка – это замена первого вхождения подслова Р в слове R на слово Q: (P, Q)=PQ.

Если PR, то говорят, что Марковская подстановка не применима к слову R. Частными случаями Марковских подстановок являются пустые вхождения:

( ,Q), (P, ), ( , ). Здесь пустые слова в скобках эквивалентны .

Пример 1:

Если R=192375923A, тогда

(923, 0000)R=1000075923

Пример 2:

Пусть R=слово, тогда

(ра, да) (не применимо)

Пример 3:

R=паровоз

(овоз, _)R=пар_

Пример 4:

R=книга

( , ) R=книга

Большинство алгоритмов не являются нормальными алгорифмами. Однако, т. к. нормальные алгорифмы описаны с полной математической строгостью и точностью, то они могут служить средством обоснования математики и использоваться при исследовании алгоритмически неразрешимых проблем на основе гипотезы, называемой принципом нормализации. Он заключается в следующем: каков бы ни был алгоритм, для которого допустимыми исходными данными и соответствующими им результатами являются слова некоторого алфавита А, всегда существует эквивалентный ему нормальный алгорифм.

2.3 Машина Тьюринга.

В 1936 г. Тьюринг предложил модель абстрактной вычислительной машины, которая уточняла понятие алгоритма и оперировала с неограниченными ресурсами.

При желании можно создать реальную модель машины Тьюринга, но ресурсы такой машины становятся ограниченными.

Машина Тьюринга преобразует какие-либо объекты (например, строку символов, принадлежащих некоторому алфавиту) в некоторый искомый результат. При этом, хотя слова алгоритма машины Тьюринга могут иметь некоторый смысл, для теории алгоритмов это несущественно.

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

А – внешний алфавит машины Тьюринга.

Некоторый алфавит Р=р₁, р₂, …р_n, характеризующий состояние машины в конкретный момент времени, называют внутренним алфавитом.

Состояние движения ленты описывается множеством возможных состояний -, …, d_j, …, d₀, d₁, …, +.

Опишем принцип работы машины Тьюринга.

1) Чтение a_i из ячейки d₀, на которой позиционируется головка чтения/записи (R/W Head). Состояние машины в этот момент определяется p_j.

Начальный кортеж: {a_i, d₀, p₀}

2) В зависимости от значений a_i и p_j изменяется поведение машины:

{a_x, d_y, p_z}

Данный кортеж означает: записать вместо a_i символ a_х, переместить головку чтения/записи в позицию d_y, блоку управления перейти в состояние p_z.

3) Если после второго шага состояние машины Тьюринга описывается исходным кортежем, то машина останавливается. Иначе – повтор пункта 2.

Компактная запись работы машины Тьюринга задается функциональной таблицей, определяющей конкретный процесс преобразования исходных данных.

	p1	p2	…	pj	…	pm
a0
a1
a2
…
ai				{ax dy pz}
…
an

Если работа машины Тьюринга конечна во времени, то говорят, что она применима к исходному данному. Некоторое слово, записанное на ленте в момент остановки машины Тьюринга, будет результатом работы.

Устройство машины Тьюринга одинаково для решения различных задач, а алфавиты А и Р – различны.

Функция, для которой существует алгоритм вычисления, называется вычислимой функцией. Если для некоторой функции f(x) существует машина Тьюринга, то говорят, что f(x) вычислима по Тьюрингу.

Тезис Тьюринга:

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

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

Описанные теории дают формальное описание понятия алгоритма, но лишь для некоторого класса алгоритмов, которые пригодны для решения ряда теоретических вопросов, но не предназначены для решения практических задач.

Было доказано, что в теоретическом отношении все рассмотренные теории эквивалентны. Это значит, что научные результаты, полученные с помощью алгоритмов, изучаемых в какой-либо из этих теорий, могут быть также получены с помощью алгоритмов, изучаемых в любой другой теории.

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