15. Рекурсивные функции.

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

Пусть задана некоторая функция  = f(x₁, x₂, …, x _n).

Здесь f (или знак функционала) – это правило, задающее связь функции и аргумента. Функционал f может быть любым, в том числе и алгоритмом.

Тогда рекурсивными функциями называют частный случай вычислимых функций. Алгоритмы, являющиеся правилами задания функций, называют алгоритмами, сопутствующими рекурсивным функциям (АСФ).

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

Базовые рекурсивные функции могут быть трех типов:

1) Функции любого числа независимых переменных, тождественно равные нулю _n()=0,где n – число аргументов функции (n может быть равным нулю).

Например:

АСФ в данном случае гласит: если задана функция _n ,то для любой совокупности значений аргументов значение функции равно нулю.

2) Тождественные функции любого числа независимых переменных _n,i, где n – число аргументов функции, i – номер одного из аргументов.

АСФ гласит: если задана функция _n,i, то значение функции равно значению i-го аргумента (слева направо).

Например:

_3,2(5, 8, 0)=8

_1,1(6)=6

Для тождественных функций:

3) Функции следования одного независимого переменного (х).

АСФ гласит: если задана функция (х), то значением функции нужно считать число, непосредственно следующее за числом, являющимся значением аргумента.

При этом (х)=х’ – последователь аргумента.

Например: (5)=5’=6

16. Алгоритмически неразрешенные проблемы.

Разделяют проблемы одиночные и массовые.

Например:

5+7=? – одиночная проблема.

х+у=? – массовая проблема.

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

Например, парадоксами являются:

1) 5-ая аксиома Евклида (Лобачевский дал ей опровержение).

2) 2*2=5

Пример 1:

10-ая проблема Гильберта.

Д. Гильберт в 1901 г. при решении диофантовых уравнений выдвинул проблему, которая гласит:

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

F(x, y, …)=0

Это – полином с целыми показателями степеней и целыми коэффициентами при неизвестных

a_nxⁿ+a_n-1x^n-1+…+a₂x²+a₁x+a₀=0

Для приведенного уравнения существует частное решение, которое заключается в том, что всякий целочисленный корень x_i является делителем a₀. При этом a₀ раскладывают на простые множители и проверяют каждый множитель на соответствие корню.

В 1970 г. ленинградский математик Ю. Матиясевич математически доказал алгоритмическую невозможность решения диофантового уравнения в общем виде.

Пример 2:

Теорема Ферма:

Не существует таких целых чисел a, b, с, n (n>2), для которых справедливо равенство

aⁿ + bⁿ = cⁿ

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

Пример 3:

Проблема Гольдбаха.

Х. Гольбах в 1742 г. в письме к Эйлеру сформулировал проблему:

Доказать, что каждое целое число N6 может быть представлено в виде суммы трех простых чисел

N=a+b+c

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

Частый случай решения этой проблемы предложил Эйлер: для четных N эта проблема разрешима и равносильна разложению на два простых слагаемых.

И. Виноградов в 1937 г. доказал, что для нечетных N можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.