Математическая логика и основы теории алгоритмов. Радаев В.Н. - 14 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

IV. Теория рекурсивных функций 13
3. Основные теоретико-числовые (арифметические) предикаты: Div(a, b),
PR(a), RP(a, b), q = Q(a, b), r = R(a, b), a = b(modk).
4. Рекурсивные функции и предикаты. Основные правила построения ре
курсивных функций и предикатов. µ-оператор Гильберта. Вычислимость
рекурсивных функций и предикатов.
5. Явные определения рекурсивных функций и предикатов. Производные
правила построения рекурсивных функций и предикатов.
6. Ограниченный µ-оператор. Ограниченные кванторы всеобщности и су
ществования. Применение ограниченных кванторов в явных определениях
рекурсивных функций и предикатов.
7. β-функция β(a, i) и ее основные свойства.
8. Теория номеров последовательностей натуральных чисел. Рекурсивные
функции и предикаты, связанные с номерами последовательностей:
<a
1
,a
2
, ..., a
n
>, lh(a), (a)
i
, ((a)
i
)
j
, Seq(a), In(a, i), a ∗ b.
9. Генерирование последовательности простых чисел по рекурсивной схе
ме. Факторизация натурального числа. Альтернативный способ нумерации
последовательностей натуральных чисел. Символ {a}
i
и рекурсивная схема
его вычисления.
10. Приведение многоместных арифметических функций и предикатов к
унарным. Свертки функций и предикатов. Формулы свертывания и развер
тывания.
11. Рекурсия пробега (возвратная рекурсия). Правило R построения ре
курсивных функций и предикатов.
12. Примитивно-рекурсивные функции и предикаты. Схемы примитивной
рекурсии для a
n
, n!, sg(n), sg(n), [
√
n], n − [
√
n]
2
(квадратичный остаток
числа n), R(a, b) (остаток от деления a на b), Q(a, b) (частное от деления
a на b), Π(n) (число простых чисел, не превосходящих n), ϕ(n) (число
чисел, не превосходящих n и взаимно простых с n), ψ(n) (число простых
делителей числа n), λ(n) (наибольший простой делитель числа n), σ(n)
(сумма всех делителей числа n).
13. Примитивная рекурсивность функций и предикатов, связанных с ну
мерацией последовательностей натуральных чисел.
14. Иные типы примитивно-рекурсивных определений: возвратная рекур
сия, одновременная рекурсия и рекурсия с замещением параметра. Приве
дение к примитивным рекурсиям.
15. Наибольший общий делитель двух натуральных чисел. Вычисление с
помощью примитивных рекурсий.
16. Рекурсивно вычислимые вещественные числа. Вычислимость чисел π
и e.
17. Рекурсивно-перечислимые предикаты. Критерий рекурсивности преди
ката (теорема Поста).
18. Тезис Черча. Эвристические доводы в пользу тезиса Черча.
Математическая логика и основы теории алгоритмов

Страницы