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

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

Литература, рекомендуемая для изучения темы
1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
Тема 38. Машины Тьюринга и невычислимые функции
Машина Тьюринга и вычислимость являются фундаментальными
понятиями математической логики. В курсовой работе необходимо изучить
основные свойства машины Тьюринга и с ее помощью построить
невычислимую функцию. Рекомендуется следующий план работы.
1 Разобрать такие основополагающие понятия математической логики,
как машина Тьюринга, вычислимая функция и тезис Черча (/1/, с. 36-54; /2/, с.
228-229, 249-255).
2 Рассмотреть понятие продуктивности машины Тьюринга и доказать ее
основные свойства (/1/, с. 46, 55-60; /2/, с. 12-25).
3 Доказать невычислимость функции продуктивность машины
Тьюринга (/1/, с. 60-64).
4 Рассмотреть проблему остановки машины Тьюринга и доказать ее
неразрешимость (/1/, с. 47-48, 53-54, 64-65).
Разобрать решения всех примеров из литературных источников /1/,/2/ и
решить задачи 3.1-3.10 из упражнения на стр. 45-48 в книге /1/.
Литература, рекомендуемая для изучения темы
1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.
2 Мендельсон Э. Введение в математическую логику. – М.: Наука,
1971.
Тема 39. Вычислимость на абаке и рекурсивные функции
Рекурсивная функция и вычислимость являются фундаментальными
понятиями математической логики. В курсовой работе необходимо изучить
вычислимость на абаке, вычислимость машиной Тьюринга и доказать их
эквивалентность понятию рекурсивной функции. Рекомендуется следующий
план работы.
1 Разобрать такие основополагающие понятия математической логики,
как машина Тьюринга, рекурсивная функция и тезис Черча (/1/, с. 36-54).
2 Рассмотреть понятие «обычного» компьютера, введенное Иоахимом
Ламбеком и названное им абаком, доказать, что вычислимость функции абаком
сводится к вычислимости ее машиной Тьюринга (/1/, с. 78-95).
3 Доказать, что рекурсивные функции вычислимы на абаках (/1/, с. 100-
122).
4 Доказать, что вычислимые функции рекурсивны (/1/, с. 100-122).
Разобрать решения всех примеров из цитированных разделов книги /1/ и
решить задачи 6.1-6.4 из упражнения на стр. 96 в книге /1/. 
        Литература, рекомендуемая для изучения темы
        1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

        Тема 38. Машины Тьюринга и невычислимые функции

       Машина Тьюринга и вычислимость являются фундаментальными
понятиями математической логики. В курсовой работе необходимо изучить
основные свойства машины Тьюринга и с ее помощью построить
невычислимую функцию. Рекомендуется следующий план работы.
       1 Разобрать такие основополагающие понятия математической логики,
как машина Тьюринга, вычислимая функция и тезис Черча (/1/, с. 36-54; /2/, с.
228-229, 249-255).
       2 Рассмотреть понятие продуктивности машины Тьюринга и доказать ее
основные свойства (/1/, с. 46, 55-60; /2/, с. 12-25).
       3 Доказать невычислимость функции продуктивность машины
Тьюринга (/1/, с. 60-64).
       4 Рассмотреть проблему остановки машины Тьюринга и доказать ее
неразрешимость (/1/, с. 47-48, 53-54, 64-65).

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

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

        Тема 39. Вычислимость на абаке и рекурсивные функции

       Рекурсивная функция и вычислимость являются фундаментальными
понятиями математической логики. В курсовой работе необходимо изучить
вычислимость на абаке, вычислимость машиной Тьюринга и доказать их
эквивалентность понятию рекурсивной функции. Рекомендуется следующий
план работы.
       1 Разобрать такие основополагающие понятия математической логики,
как машина Тьюринга, рекурсивная функция и тезис Черча (/1/, с. 36-54).
       2 Рассмотреть понятие «обычного» компьютера, введенное Иоахимом
Ламбеком и названное им абаком, доказать, что вычислимость функции абаком
сводится к вычислимости ее машиной Тьюринга (/1/, с. 78-95).
       3 Доказать, что рекурсивные функции вычислимы на абаках (/1/, с. 100-
122).
       4 Доказать, что вычислимые функции рекурсивны (/1/, с. 100-122).

      Разобрать решения всех примеров из цитированных разделов книги /1/ и
решить задачи 6.1-6.4 из упражнения на стр. 96 в книге /1/.

Страницы