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

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

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

Пусть 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=книга

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

13. Гипотеза Черча.

Гипотеза Черча: понятием рекурсивной функции исчерпывается полностью понятие вычислимой функции.

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

Невозможность создания рекурсивной функции для решаемой задачи означает невозможность реализации алгоритма ее решения.

Гипотеза Черча и ее обобщение не имеет доказательства, потому что она оперирует нематематическими понятиями алгоритма в интуитивном смысле.

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

В 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

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