Сборник тем курсовых работ по математике (алгебра, математическая логика, дискретная математика). Молчанов В.А - 23 стр.

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

        Тема 36. Нестандартные модели арифметики

         В любой математической теории принципиально важным является
вопрос о существовании и единственности модели формализации этой теории.
В курсовой работе          необходимо проанализировать этот вопрос для
элементарной теории арифметики. Рекомендуется следующий план работы.
         1 Рассмотреть язык логики узкого исчисления предикатов арифметики
и его стандартную интерпретацию в алгебре натуральных чисел(/1/, с. 131-151;
/2/, с. 115-131).
         2 Доказать теорему о существовании нестандартных моделей
элементарной теории арифметики (/1/, с. 252-260).
         3 Изучить метод построения моделей элементарной теории арифметики
с помощью принципов нестандартного анализа (/1/, с. 25-32; /3/, с. 57-79).

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

        Литература, рекомендуемая для изучения темы
        1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
        2 Мендельсон Э. Введение в математическую логику. – М.: Наука,
1971.

        Тема 37. Метод диагонализации в математической логике

       В математической логике, теории множеств и других разделах
математики широко применяется метод диагонализации, в основе которого
лежит возможность построения антидиагонального счетного множества для
любой последовательности счетных множеств. В курсовой работе необходимо
изучить метод диагонализации и с его помощью построить примеры
невычислимых функций. Рекомендуется следующий план работы.
       1 Рассмотреть понятие счетного множества и изучить метод
диагонализации (/1/, с. 12-30).
       2 Рассмотреть понятие машины Тьюринга и методом диагонализации
построить пример невычислимой функции (/1/, с. 36-45, 66-74).
       3 Рассмотреть проблему остановки машины Тьюринга и с помощью
тезиса Черча доказать ее неразрешимость (/1/, с. 47-48, 74-76).
       4 Рассмотреть понятие диагонализации выражения и доказать лемму о
диагонализации и теорему Черча о неразрешимости (/1/, с. 228-235).

      Разобрать решения всех примеров из цитированных разделов /1/ и
решить задачи 3.9, 3.10 из упражнения на стр. 45-48 и задачи 5.1-5.4 из
упражнения на стр. 76-77 в книге /1/.