Второй тип алгоритмических моделей.

Второй тип алгоритмических моделей связывает понятие алгоритма с наиболее традиционными понятиями математики - вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа - рекурсивные функции - является исторически первой формализацией понятия алгоритма.

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

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

Как задать и как вычислить функции.

Теория рекурсивных функций строится в два приема. (с38)

Определяются примитивно-рекурсивные функции.

Эти операторы сохраняют вычислимость.

Оператор суперпозиции. (с39)

Примеры (с40)

Суперпозиция функций:

Оператор примитивной рекурсии (с41)

Оператор примитивной рекурсии задается следующим образом:

Рекурсия ведется по одному аргументу, все остальные считаются параметрами.

В нуле функция равна функции g, а в некоторой точке y+1 она определяется через известную функцию h и значение этой же функции в предыдущей точке.

Приведенная пара равенств называется схемой примитивной рекурсии.

Принципиальная разница между рекурсией и суперпозицией в том, что для вычисления значения в точке y+1 нужно вычислить значение во всех предыдущих точка.

Оператор минимизации (с42)

Минимизация. Скажем, что функция Fⁿ(x₁,... ,x_n) получена с помощью оператора минимизации( -оператора) из функции gⁿ⁺¹(x₁,..., x_n,y), если Fⁿ(x₁,...,x_n) определена и равна y тогда и только тогда, когда все значения gn+1(x1,..., xn,0),...,gn+1(x1,..., xn,y-1) определены и не равны 0, а gn+1(x1,..., xn,y)=0. Каково минимальное значение у, при котором g(x1, …, xn, y) = 0 ?

В этом случае будем писать

Примитивно-рекурсивные и частично-рекурсивные функции. (с43)

Функция называется примитивно – рекурсивной, если она может быть получена из константы 0 и функции x^’ с помощью конечного числа применений операторов тождества, суперпозиции и п-р.

Большинство вычислимых функций относится к классу примитивно-рекурсивных функций.

Если некоторые функции являются примитивно-рекурсивными, то в результате применения к ним операторов суперпозиции или примитивной рекурсии можно получить новые примитивно-рекурсивные функции.

Существует три возможности доказательства того, что функция является примитивно-рекурсивной:

а) показать, что заданная функция является простейшей;

б) показать, что заданная функция построена с помощью оператора суперпозиции;

в) показать, что заданная функция построена с помощью оператора примитивной рекурсии.

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

Функция называется частично-рекурсивной (вычислимой по Черчу), если она может быть получена из простейших функций с помощью конечного числа операторов суперпозиции, примитивной рекурсии и минимизации.

Указанные операции могут быть выполнены в любой последовательности и любое конечное число раз.

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

Если такие функции оказываются всюду определенными, то они называются общерекурсивными функциями.

Частично-рекурсивные функции вычислимы путем определенной процедуры механического характера. Практически понятием частично-рекурсивных функций пользуются для доказательства алгоритмической разрешимости или неразрешимости проблем.

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

Всякая частично рекурсивная функция вычислима на машине Тьюринга.

Всякая примитивно рекурсивная функция f является всюду определенной функцией.

Примеры: (с44-46)

Частичная рекурсивность основных операций арифметики.

Функция константа: f(x) = m s(s(s…s(Z(x))…)) m-раз.

Операция сложения, определенная через оператор примитивной рекурсии:

f(x,y)=x+y

f(x,0)=x;

f(x,y+1)=x+(y+1)=(x+y)+1=f(x,y)+1

Покажем, что данная схема соответствует схеме примитивной рекурсии: f(x,0)=g(x)=x=I(x);

f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) = s(f(x,y)) = s(I₃³ (x,y,f(x,y))

+² =R(I₁¹,[s¹;I₃³]).

Операция умножения, определенная через оператор примитивной рекурсии:

f(x,y)=x*y

f(x,0)=x*0=0;

f(x,y+1)=x*(y+1)=x*y+x=f(x,y)+x

Покажем, что данная схема соответствует схеме примитивной рекурсии: f(x,0)=g(x)=0=Z(x);

f(x,y+1) = h(x,y,z) = h(x,y,f(x,y)) =x+z= I₃¹ (x,y,f(x,y))+ I₃³ (x,y,f(x,y))

x² =R(Z,[+;I₃³,I₁³])

Усеченная разность

Мы говорим об " усеченном вычитании"

поскольку мы имеем дело только с натуральными (целыми неотрицательными) числами.

Одноместная функция усеченного вычитания единицы определяется рекурсивно:

f(0) =0

f(x+1) =x+1 f(x+1)=h(x,f(x))=I₁²(x,f(x));

Рекурсия здесь формальна, так как предыдущее значение не используется.

После этого усеченное вычитание для произвольных аргументов можно определить так:

f(x,0) =x

f(x,y+1)=x

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

f(x,0)=g(x)=x=I(x);

f(x,y+1) = I₃³ (x,y,f(x,y)

Использование оператора минимизации. (с47)

Используя минимизацию можно получать частично – определенные функции из всюду определенных функций.

Пример 3.

Пусть f(x,y)=|x-y²|. Определим φ(x)=μy[|x-y²|=0].

φ(x) = , если x точный квадрат и неопределенна в противном случае.

Лекция №4.

Нормальные алгоритмы Маркова. Контекстно-свободные грамматики. Определение понятия формального языка, грамматика языка, язык грамматики. Классификация формальных грамматик по Хомскому.