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=слово, тогда

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

Пример 3:

R=паровоз

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

Пример 4:

R=книга

( , ) R=книга

Большинство алгоритмов не являются нормальными алгорифмами.

Однако, т. к. нормальные алгорифмы описаны с полной математической

строгостью и точностью, то они могут служить средством обоснования

математики и использоваться при исследовании алгоритмически

неразрешимых проблем на основе гипотезы, называемой принципом

нормализации. Он заключается в следующем: каков бы ни был алгоритм, для

которого допустимыми исходными данными и соответствующими им

результатами являются слова некоторого алфавита А, всегда существует

эквивалентный ему нормальный алгорифм.

17

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

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

полностью понятие вычислимой функции.

Какова бы ни была вычислимая неотрицательная целочисленная

функция от неотрицательных целочисленных аргументов существует

тождественно равная ей рекурсивная функция.

Проводя аналогию этого тезиса с алгоритмами, состоящими из простых

операций, можно сказать:

Каков бы ни был алгоритм, перерабатывающий наборы целых

неотрицательных чисел в целые неотрицательные числа, существует

алгоритм, сопутствующий рекурсивной функции, который ему

эквивалентен.

На основе этой гипотезы российские ученые А.Н.Колмогоров и

В.А.Успенский сделали обобщение: если существует некоторая рекурсивная

функция, то для нее всегда можно построить алгоритм. И наоборот, любой

существующий алгоритм может быть выражен в понятиях рекурсивной

функции.

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

означает невозможность реализации алгоритма ее решения.

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

оперирует нематематическими понятиями алгоритма в интуитивном смысле.

18

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

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

машины, которая уточняла понятие алгоритма и оперировала с

неограниченными ресурсами. При желании можно создать реальную модель

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

Машина Тьюринга преобразует какие-либо объекты (например, строку

символов, принадлежащих некоторому алфавиту) в некоторый искомый

результат. При этом, хотя слова алгоритма машины Тьюринга могут иметь

некоторый смысл, для теории алгоритмов это несущественно.

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

последовательным доступом.

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

Некоторый алфавит Р=р1, р2, …рn, характеризующий состояние машины в

конкретный момент времени, называют внутренним алфавитом.

Состояние движения ленты описывается множеством возможных

состояний

-, …, dj, …, d0, d1, …, +.

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

1) Чтение ai из ячейки d0, на которой позиционируется головка

чтения/записи (R/W Head). Состояние машины в этот момент определяется pj.

Начальный кортеж: {ai, d0, p0}

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

{ax, dy, pz}

Данный кортеж означает: записать вместо ai символ aх, переместить

головку чтения/записи в позицию dy, блоку управления перейти в состояние pz.

3) Если после второго шага состояние машины Тьюринга описывается

исходным кортежем, то машина останавливается. Иначе – повтор пункта 2.

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

определяющей конкретный процесс преобразования исходных данных.

p1 p2 … pj … pm

a0

a1

19

- d + 0 a0A

Блок

управления

R/W Нead

…a

i {ax dy pz}

…a

n

Если работа машины Тьюринга конечна во времени, то говорят, что она

применима к исходному данному. Некоторое слово, записанное на ленте в

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

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

а алфавиты А и Р – различны.

Функция, для которой существует алгоритм вычисления, называется

вычислимой функцией. Если для некоторой функции f(x) существует машина

Тьюринга, то говорят, что f(x) вычислима по Тьюрингу.

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

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

Тьюринга, реализующую её.

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

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

используется в теории алгоритмов для доказательства разрешимости

проблем.

Описанные теории дают формальное описание понятия алгоритма, но

лишь для некоторого класса алгоритмов, которые пригодны для решения

ряда теоретических вопросов, но не предназначены для решения

практических задач. Было доказано, что в теоретическом отношении все

рассмотренные теории эквивалентны. Это значит, что научные результаты,

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

могут быть также получены с помощью алгоритмов, изучаемых в любой

другой теории.

Основной тезис в каждой из теорий позволяет выявлять случаи

невозможности построения алгоритмов для заданного класса проблем, но не

позволяет получить эффективные алгоритмы решения разрешимых проблем

на практике.

20