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

Министерство образования Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет математики и информационных технологий

Кафедра алгебры и дискретной математики

КУРСОВАЯ РАБОТА

по дисциплине «Дискретная математика»

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

Руководитель работы

_______________Усова Л. Б.

«_____» _______________ 2016г

Исполнитель

Студент гр. 15МКН(ба)АПКМ

______________Петин А. Д.

«_____» _______________ 2016г

Оренбург 2016

Задание

В курсовой работе необходимо изучить основные свойства машины Тьюринга и с ее помощью построить невычислимую функцию.

Содержание

Введение …………………………………………………………………Стр. 3

1. Описание машины Тьюринга ……………………………………..…Стр. 4 

2. Примеры некоторых машин Тьюринга:

2.1. Машина Тьюринга, которая  записывает на пустую ленту 3 символа S1, следующим образом -  S1S1S1 ......................................................................Стр. 5

2.2. Машина, удваивающая число последовательно записанных единиц …………………………………………………………………………………...Стр. 6

2.3. Машина Тьюринга, записывающая 2n единиц на изначально пустой ленте ……………………………………………………………………………Стр. 8

3. Вычислимая функция ………………………………………………..Стр. 9

4. Тезис Чёрча ………………………………………………………….Стр. 10

5. Продуктивность машины Тьюринга ……………………………….Стр. 10

6. Основные свойства машины Тьюринга ……………………………Стр. 11

7. Функция продуктивности машины Тьюринга. Некоторые ее свойства ………………………………………………………………………………… Стр. 12

8. Невычислимость функции продуктивности машины Тьюринга ...Стр. 16

9. Проблема остановки машины Тьюринга и ее неразрешимость ….Стр. 18

Список использованных источников …………………………………Стр. 19

Введение

Алан Тьюринг окончил Кембриджский университет в 1935 г. В это время внимание многих математиков было приковано к работам, посвященным логическим основам математики. Её фундаментальные понятия подверглись тщательному изучению и обоснованию. Особенно те, которые традиционно использовались без уточнения их смысла, на интуитивном уровне.

Алгоритм – одно из таких понятий. А. Тьюрингу удалось дать определение понятия "алгоритм". В качестве уточнения понятия он предложил некоторую гипотетическую конструкцию – машину, получившую вскоре название "машина Тьюринга". Он сделал свое изобретение в 1937 г. В то время Тьюринг стажировался в Принстонском университете в США. В Англию он вернулся знаменитым ученым.