SHPORA.net :: PDA

[ Back ]

Пусть задана некоторая функция f(x,y). Зафиксируем значение х и выясним, при каком у f(x,y) = 0.

Более сложная задача, найти наименьшее у, такое, что:<*>(x) =<*>y[f(x,y) = 0].

Наименьшее у, такое, что f(x,y) = 0.

Аналогично:<*>(x1, ..., xn) =<*>y[f(x1, ..., xn, y) = 0];<*>получается применением<*>-оператора.

Замечание 1: для вычисления<*>(x1, ..., xn) можно предложить последовательно вычислить, сравнивая с нулём f(x1, ..., xn,



0)<*>0; f(x1, ..., xn, 1)<*>0; ...; f(x1, ..., xn, k) = 0.

Замечание 2:<*>(x1, ..., xn) неопределенна, если везде<*>0 или до 0 f неопределенна.

Пример: f(x,y) = x-y;

f(x,y) =<*>z[y+z=x] =<*>z[I32(x,y,z)+I33(x,y,z)+ (x,y,z)].

Для вычисления f(5,2), т. е. у=2, х=5, необходимо при у=2 придать х последовательно значения:

z = 0 2+0 = 2<*>5

z = 1 2+1 = 3<*>5

z = 2 2+2 = 4<*>5

z = 3 2+3 = 5 = 5

т. е. f(5,2) = 3

Функция f(x1, ..., xn) называется частично рекурсивной, если она может быть получена за конечное число шагов из простейших



функций при помощи операторов: подстановки, рекурсии и<*>-оператора.

Теорема: класс частично рекурсивных функций равномощен классу функций, вычислимых по Тьюрингу.

Функция f(x1, ..., xn) называется обще-рекурсивной, если она частично рекурсивна и всюду определена.

Например: S(x), O(x), Inm(x1, ..., xn), x+y, x*y, x+n, ...



Пусть А – алфавит. Нормальный алгоритм Маркова задается алфавитом А и нормальной схемой подстановок.

Алфавит – конечное непустое множество элементов, называемых буквами. Конечные последовательности букв образуют слова (в том



числе и пустые).

Нормальная схема подстановок – это конечный набор, состоящий из пар слов(подстановок)<*>-><*>(подстановка)



или<*>->•<*>(конечная подстановка), где левое слово переходит (заменяется) в правое (но не наоборот)

Нормальная схема подстановок U.

<*>1-><*><*>1;

…

ak-><*>bk, ai->bi<*>A*, i=0,1,2,…,k

Принято говорить, что слово Т входит в слово Q, если существуют такие (возможно пустые слова) W и V, что Q=WTV.

Опишем следующий алгоритм переработки любого слова Р в алфавите А.

Находим в схеме U подстановку Рi <*>Qi, такую, что Рi входит в Р и самое левое вхождение Рi заменяется на Qi. Если это



конечная подстановка, то процесс приостанавливается. Он приостанавливается так же, когда нет ни одной подстановки левее



слова, которое входит в слово на котором мы останавливаемся. Последнее слово на котором мы остановились и является



результатом переработки слова Р схемой U.

U(P)=P’.

Если подстановка совершилась и она не конечная, и R – результат подстановки, полученной из слов Р, то аналогичное



осуществляется со словом R.

Итак, если процесс обрывается (нет ни одной применимой подстановки) на слове Q или процесс приходит в конечную подстановку



(наличие •- точки), то говорят, что алгоритм слово Р перевел в слово Q.

Описанный алгоритм и называется нормальным алгоритмом Маркова.

Тезис Маркова: Всякий интуитивный алгоритм представим в виде нормального алгоритма Маркова.

Теорема: Класс нормальных алгоритмов совпадает с классом алгоритмов Тьюринга и с классом частично рекурсивных функций.