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

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

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

любой алгоритм является рекурсией, и наоборот.

Пусть задана некоторая функция = f(x1, x2, …, x n).

Здесь f (или знак функционала) – это правило, задающее связь функции и

аргумента. Функционал f может быть любым, в том числе и алгоритмом.

Тогда рекурсивными функциями называют частный случай вычислимых

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

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

В основе теории рекурсий лежат ограниченные множества базовых

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

формируются новые функции. Если рассматривать операторы как алгоритмы,

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

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

1) Функции любого числа независимых переменных, тождественно

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

нулю).

Например:













v f x x x x

z x y x y

y x

n n ( , ,..., ),

( , , ), , ,

( )

1 2

2

1





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

совокупности значений аргументов значение функции равно нулю. Например,

1 (0 ) 0 ,3 (3,5,7) 0 .

2) Тождественные функции любого числа независимых

переменных n,i, где n – число аргументов функции, i – номер одного из

аргументов.

АСФ гласит: если задана функция n,i, то значение функции равно

значению i-го аргумента (слева направо).

Например:

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

1,1(6)=6

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

i 0 , n 0

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

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

считать число, непосредственно следующее за числом, являющимся

значением аргумента.

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

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

Знак апострофа показывает на получение последователя для x.

21

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

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

Например:

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

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

Принципиально неразрешимыми должны быть алгоритмы получения

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

бы существование парадоксальных объектов.

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

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

2) 2*2=5

Пример 1:

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

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

проблему, которая гласит:

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

произвольного диофантового уравнения

F(x, y, …)=0

Это – полином с целыми показателями степеней и целыми

коэффициентами при неизвестных

anxn+an-1xn-1+…+a2x2+a1x+a0=0

Для приведенного уравнения существует частное решение, которое

заключается в том, что всякий целочисленный корень xi является делителем

a0. При этом a0 раскладывают на простые множители и проверяют каждый

множитель на соответствие корню.

В 1970 г. ленинградский математик Ю. Матиясевич математически

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

общем виде.

Пример 2:

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

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

справедливо равенство

an + bn = cn

Эта теорема была доказана для многих значений n и проверена для

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

теоремы.

Пример 3:

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

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

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

суммы трех простых чисел

N=a+b+c

Это значит, что нужно найти алгоритм, который позволил бы для любого

целого числа N6 найти хотя бы одно разложение на три простых слагаемых.

22

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

эта проблема разрешима и равносильна разложению на два простых

слагаемых.

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

простых слагаемых, но для четных чисел решение не найдено до сих пор.

23