ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 14.02.2021
Просмотров: 140
Скачиваний: 1
Рекурсивные
функции
Всякий
алгоритм
однозначно
ставит
в
соответствие
исходным
данным
(
в
случае
,
если
он
определен
на
них
)
результат
.
Поэтому
с
каждым
алгоритмом
однозначно
связана
функция
,
которую
он
вычисляет
.
Верно
ли
обратное
:
для
всякой
ли
функции
существует
вычисляющий
ее
алгоритм
?
Исследование
проблемы
остановки
для
машин
Тьюринга
показывает
,
что
нет
:
для
предиката
Р
(
Т
,
а
),
истинного
,
если
и
только
если
машина
Тьюринга
Т
останавливается
при
исходных
данных
а
,
алгоритма
его
вычисления
не
существует
.
Возникает
вопрос
:
для
каких
функций
алгоритмы
существуют
?
Как
описать
такие
алгоритмические
,
эффективно
вычислимые
функции
?
Исследование
этих
вопросов
привело
к
созданию
в
30-
х
годах
нашего
века
теории
рекурсивных
функций
.
В
этой
теории
,
как
и
вообще
в
теории
алгоритмов
,
принят
конструктивный
,
финитный
подход
,
основной
чертой
которого
является
то
,
что
все
множество
исследуемых
объектов
(
в
данном
случае
функций
)
строится
из
конечного
числа
исходных
объектов
-
базиса
-
с
помощью
простых
операций
,
эффективная
выполнимость
которых
достаточно
очевидна
.
Одним
из
наиболее
распространенных
вариантов
математического
уточнения
понятия
вычислимой
арифметической
функции
,
аргументы
и
значения
которой
–
натуральные
числа
,
является
рекурсивная
функция
.
Рекурсивные
функции
являются
частичными
функциями
,
т
.
е
.
функциями
,
не
обязательно
всюду
определенными
.
Чтобы
подчеркнуть
это
обстоятельство
,
часто
в
качестве
синонима
используют
термин
“
частично
рекурсивные
функции
”.
Рекурсивные
функции
,
определенные
при
любых
значениях
аргументов
,
называют
общерекурсивными
функциями
.
Определению
рекурсивной
функции
может
быть
придана
следующая
форма
.
Фиксируется
небольшое
число
чрезвычайно
простых
исходных
вычислимых
функций
:
O(x)
= 0,
S(x)
=
x
+ 1,
)
1
(
)
,...,
(
1
n
m
x
x
x
I
m
n
n
m
≤
≤
=
;
фиксируется
также
небольшое
число
операций
над
функциями
,
переводящих
вычислимые
функции
снова
в
вычислимые
:
подстановки
,
примитивной
рекурсии
и
минимизации
.
Оператор
подстановки
сопоставляет
функции
f
от
n
переменных
и
функциям
g
1
,…,g
n
от
m
переменных
функцию
h
от
m
переменных
такую
,
что
для
любых
натуральных
чисел
x
1
,…,
x
m
))
,...,
(
),...,
,...,
(
(
)
,...,
(
1
1
1
1
x
x
g
x
x
g
f
x
x
h
m
n
m
m
≅
Оператор
примитивной
рекурсии
сопоставляет
двум
функциям
f
от
n
переменных
и
g
от
n+2
переменных
такую
функцию
h
от
n+1
переменных
,
что
для
любых
натуральных
чисел
x
x
n
,...,
1
,
y
))
,...,
(
)
0
,
,...,
(
1
1
x
x
f
x
x
h
n
n
≅
,
))
,
,...,
(
,
,
,...,
(
)
,
,...,
(
1
1
1
1
y
x
x
h
y
x
x
g
x
x
h
n
n
n
y
≅
+
Оператор
минимизации
сопоставляет
функции
f
от
n+1
переменных
функцию
h
от
n
переменных
такую
,
что
для
любых
натуральных
чисел
x
x
n
,...,
1
,
y
y
x
x
h
n
=
)
,...,
(
1
тогда
и
только
тогда
,
когда
)
,
,...,
(
),...,
,
,...,
(
1
0
1
1
−
y
x
x
f
x
x
f
n
n
определены
и
отличны
от
0
,
а
)
,
,...,
(
1
y
x
x
f
n
определена
и
равна
0;
если
же
y
с
указанными
свойствами
не
существует
то
значение
)
,...,
(
1
x
x
h
n
считается
неопределенным
.
Если
функция
h
получена
из
функции
f
с
помощью
оператора
минимизации
,
то
обычно
пишут
:
)
0
)
,
,...,
(
(
)
,...,
(
1
1
=
≅
y
x
x
f
y
x
x
h
n
n
µ
Рекурсивные
функции
уже
в
силу
характера
своего
определения
оказываются
вычислимыми
.
В
известном
смысле
верно
и
обратное
:
имеются
серьезные
основания
считать
,
что
математическое
по
своему
характеру
понятие
рекурсивности
является
точным
эквивалентом
несколько
расплывчатого
представления
о
вычислимости
.
В
1936
г
.
А
.
Черчем
был
сформулирован
тезис
:
класс
функций
,
вычислимых
с
помощью
алгоритмов
в
широком
интуитивном
смысле
,
совпадает
с
классом
частично
рекурсивных
функций
.
