Задача точного определения понятия алгоритма была полностью решена в 30-х годах XX века в двух формах: на основе описания алгоритмического процесса и на основе понятия рекурсивной функции

Вид материала

Задача

Содержание § 4.2. Примитивно-рекурсивные функции § 4.3. Частично рекурсивные функции Функция называется частично-рекурсивной, если она может быть получена из простейших функций C 5+z=3 будет иметь значение «истина», так и не наступит, а значит значение функции μ Mf(x) используется запись f § 4.4. Общерекурсивные функции § 4.5. Задание рекурсивных функций Е(х) всегда равна нулю, и для F(1) 4.5.2. Дополнительные способы задания примитивно-рекурсивных функций Пусть заданы некоторые функции f § 4.6. Мажорируемые неявные функции § 4.7. Возвратная рекурсия и функция Фибоначчи Ф(n) в точке n=0 Ф(n) – возвратная рекурсия из функций h(n, a § 4.8. Эффективная перечислимость и распознаваемость § 4.9. Нерекурсивные и непримитивно рекурсивные функции Непримитивно рекурсивной § 4.10. Границы применимости формальных моделей алгоритмов Задачи к Главе 4

Подобный материал:

• Ю. А. Самарский 10 июня 2011 г. Программа, 140.09kb.
• Обеспечение производства ЭВМ базовые понятия (сапр/астпп/саит), 710.17kb.
• Программа по дисциплине информатика (алгоритмы и алгоритмические языки). Основной курс, 103.21kb.
• Программа по дисциплине: информатика (алгоритмы и алгоритмические языки). Продвинутый, 140.13kb.
• -, 136.86kb.
• Оценка стоимости месторождения нефти на основе применения метода реальных опционов, 86.25kb.
• 1. Функции нескольких переменных. Основные понятия. Область определения, 13.11kb.
• Тема: Основные понятия и определения, 164.71kb.
• Вопросы к экзамену по дисциплине "физическая химия", 62.78kb.
• Киприан Керн, 251.05kb.

Глава 4. Рекурсивные

функции

§ 4.1. Роль рекурсивных функций

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

Первый подход подробно описан в Главе 1 и заключается в том, что был сконструирован формальный автомат, способный осуществлять ограниченный набор строго определённых элементарных операций (машина Тьюринга). Алгоритмом стали называть конечную последовательность таких операций и постулировали предложение, что любой интуитивный алгоритм является алгоритмом и в сформулированном выше смысле. То есть для каждого алгоритма можно подобрать реализующую его машину Тьюринга.

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

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

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

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

При этом, если получается сделать алгоритм без применения рекурсии, то, скорее всего, им и надо воспользоваться. Рекурсивные вызовы подпрограмм имеют свойство решать одну и ту же задачу бесчисленное количество раз (во время повторов), что значительно сказывается на времени.

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

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


.

§ 4.2. Примитивно-рекурсивные функции

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

В качестве базисных функций обычно берутся следующие:

• Функция следования;
  
• Функция тождества (функция проекции, или функция выбора аргументов);
  
• Функция константы.
  

Допустимыми операциями над функциями являются операции суперпозиции (подстановки) и примитивной рекурсии.


Частичная арифметическая функция f называется примитивно-рекурсивной, если она может быть получена из простейших функций C_qⁿ, S, U_mⁿ конечным числом операций подстановки и примитивной рекурсии (т.е. задана в базисе Клини).


Т.о. базис Клини состоит из:

• трех простых функций;
  
• двух разрешенных операций.
  

Рассмотрим сначала функции.

1) функция – следование: S(x) = x' = x+1, где x’ – число, непосредственно следующее за натуральным числом х. Например, 0’ = 1, 1’ = 2, … и т.д.

2) функция - тождество: , где n – кол-во переменных, а i – номер переменной, по которой берется тождество. Функция тождества – функция, равная одному из своих аргументов. Например, .

3) функция - константа: , где n – число переменных, q – значение, которое принимает функция. Функция константа принимает всюду одно значение. Например, C₂³(16,9,10)=2.

Далее рассмотрим операции.

1) операция примитивной рекурсии R

Если мы имеем функцию одной переменной f(x), то схема рекурсии называется «рекурсия без параметров» и задается системой уравнений:

f (0) = q

f (x') = χ (f (x), x)

Функция, заданная такими уравнениями, кратко задается схемой вида R_q ( χ ). Поскольку вид системы уравнений (и способ задания трех разрешенных функций) строго определен, то схема является однозначной.

Если мы имеем функцию нескольких переменных f(x₁,x₂,…,x_n), то схема рекурсии называется «рекурсия с параметрами» и задается системой уравнений:

f (0, x₂,…, x_n) = Ψ (x₂,…, x_n)

f (x'₁, x₂,…, x_n) = χ (f(x₁,…, x_n), x₁,…, x_n)

Функция, заданная такими уравнениями, кратко задается схемой вида Rⁿ (Ψ, χ)


2) операция подстановки (суперпозиции) S:

Пусть заданы m каких либо частичных арифметических функций f₁, f₂,…f_m от одного и того же числа n переменных, определенных на множестве А со значениями в множестве В. Пусть на множестве В задана частичная функция Ф от n переменных, значения которой принадлежат множеству С. Введем теперь частичную функцию g от n переменных, определенную на А со значениями в С, полагая по определению для произвольных x₁,…,x _n.

g(x₁,…, x _n) = Φ (f₁ (x₁,…, x _n), f₂ (x₁,…, x _n),…, f _m (x₁,…, x _n ))

Говорят, что функция g получается операцией суперпозиции или подстановки из функций f₁, f₂,…,f_m. Обозначается эта операция буквой S с двумя индексами: верхний (n) показывает от скольких переменных зависят внутренние функции f_i (x₁,…, x _n), а нижний (m) – количество самих функций f₁, f₂,…,f_m.

_n

g(x₁,…, x _n) = S _m (Φ, f₁, f₂,…, f _m),

При этом функция Ф при подсчете внутренних функций не учитывается.

§ 4.3. Частично рекурсивные функции

Класс частично-рекурсивных функций определяется путем указания конкретных исходных функций и фиксированного множества операций получения новых функций из ранее заданных.

В качестве базисных функций обычно берутся следующие:

• Функция следования;
  
• Функция тождества (функция проекции, или функция выбора аргументов);
  
• Функция константы.
  

Допустимыми операциями над функциями являются операции суперпозиции (подстановки), примитивной рекурсии и минимизации.




Функция называется частично-рекурсивной, если она может быть получена из простейших функций C_qⁿ, S, U_mⁿ конечным числом операций подстановки, примитивной рекурсии и минимизации (т.е. задана в расширенном базисе Клини).


Т.о. расширенный базис Клини состоит из:

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