8. Представимость рекурсивных функций и отрицательные резуль­таты ма­тематической логики.

Главными отрицательными результатами теории алгоритмов являются тео­рема Черча о неразрешимости, теорема Тарского о неопределимости истинности и первая теорема Геделя о неполноте систем арифметики. Цель данной работы – изучить доказательства этих теорем с по­мощью представления рекур­сивных функций в специальном расширении арифметики.

Рекомендуется следующий план работы:

1. Разобрать такие основополагающие понятия теории алгоритмов,

как язык арифметики и рекурсивная функция (/1/, с. 103-108, 141-145).

2. Рассмотреть понятие представимости функций в теории и доказать

представимость рекурсивных функций в специальном непротиворечивом расширении Q арифметики (/1/, с. 212-226).

3. Рассмотреть понятие геделевой нумерации и доказать главные

отрицательные результаты теории алгоритмов (/1/, с. 228-240).

4. Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 14.1-14.2 из упражнения на стр. 226-227 и задачи 15.1-15.4 из упражнения на стр. 240 в книге /1/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

9. Разрешимость арифметики сложения.

Проблема разрешимости теорий имеет принципиальное значение для эле­ментарно аксиоматизируемых математических теорий и, в частности, для ариф­метики. Цель данной работы – проанализировать эту проблему для арифметики с различными основными операциями.

Рекомендуется следующий план работы:

1. Разобрать такие основополагающие понятия математической ло­гики, как геделева нумерация и разрешимое множество (/1/, с. 228-233, /2/, с.151-152).

2. Доказать неразрешимость арифметики со сложением и умноже­нием (/1/, с. 234-236).

3. Доказать разрешимость арифметики со сложением, без умноже­ния (/1/, с. 290-299).

4. Разобрать решения всех примеров из цитированных разделов книг /1/,/2/ и решить задачи 1-3 из упражнения на стр. 152 в книге /2/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

10. Теорема Геделя о неполноте формальной арифметики.

Теорема Геделя о неполноте формальной арифметики по праву счи­тается одним из наиболее замечательных достижений математической ло­гики и теории алгоритмов, поскольку в своей семантической формули­ровке устанавливает не­возможность доказательства любого истинного ут­верждения этих формальной теории. Цель данной работы - изу­чить основы формальной арифме­тики и разобрать доказательство семан­тической формулировки теоремы Геделя о ее неполноте.

Рекомендуется следующий план работы:

1. Изучить постановку задачи о неполноте формальной арифметики (/1/,с. 7-11).

2. Рассмотреть начальные понятия теории алгоритмов и примеры их

применения (/1/, с. 12-21).

3. Доказать простейшие критерии неполноты (/1/, с. 21-25).

4. Изучить основы формальной арифметики и доказать семантиче­скую формулировку теоремы Геделя о ее неполноте (/1/, с. 25-42).

5. Разобрать все примеры и восстановить все пропущенные доказа­тельства в брошюре /1/.

Литература, рекомендуемая для изучения темы:

1. Успенский В.А. Теорема Геделя о неполноте. – М.: Наука, 1982.