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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

14
VI. Арифметизация процесса логического вывода. Рекурсивная неразрешимость и
дедуктивная неполнота формальной арифметики
V. Теория алгоритмов
1. Понятие об алгоритме. Основные признаки алгоритмичности разрешаю
щей процедуры.
2. Теория нормальных алгоритмов Маркова.
3. Эффективно вычислимые по Маркову функции. Принцип нормализации
Маркова. Эквивалентность принципа нормализации тезису Черча.
4. Алгоритмы Тьюринга и их реализация на машине Тьюринга. Эквива
лентность понятий эффективной вычислимости по Маркову и Тьюрингу.
5. Исчисление равенств ЭрбранаГеделя. ЭГ-вычислимые функции. Экви
валентность рекурсивной и ЭГ-вычислимости.
6. Исчисление λ-конверсии Черча. λ-определимость и эффективная вычис
лимость.
7. Понятие о сложности алгоритма.
VI. Арифметизация процесса логического вывода.
Рекурсивная неразрешимость и дедуктивная
неполнота формальной арифметики
1. Рационализация логической символики и схем построения термов и фор
мул формального исчисления. Указатели (выражения). Индексы. Теорема
о построении указателей.
2. Нумерация символов и указателей формального исчисления. Индуктив
ная схема вычисления номера указателя. Однозначность характеризации
указателя его номером. Вычислимость множества номеров указателей фор
мального исчисления. Нумерация символов и указателей исчисления пре
дикатов и формальной арифметики.
3. Рекурсивные функции и предикаты, связанные с номерами термов и
формул теоретико-числовой системы Z: Vble(a), Term(a), AFor(a), For(a),
Sub(a, b, c), Fr(a, b), Subtl(a, b, c), PAx
1−6
(a), NLAx(a), Ax(a), MP(a, b, c),
PI
1
(a, b), PI
2
(a, b), I(a, b, c).
4. Нумерация последовательностей формул формального исчисления. Пре
дикаты Prf(a) и Pr(a, b).
5. Множество номеров теорем формального исчисления. Предикат Thm(a).
Рекурсивно-аксиоматизируемые и рекурсивно-аксиоматизированные фор
мальные системы первого порядка. Рекурсивная перечислимость множе
ства номеров теорем рекурсивно-аксиоматизированного формального ис
числения.
6. Представимость (выразимость) и сильная представимость функций и
предикатов формулами и термами теоретико-числовой системы Z.Теоре
ма о возможности представления рекурсивных функций и предикатов фор
Ю.Н. Радаев

Страницы