Автор работы: Пользователь скрыл имя, 21 Сентября 2015 в 11:45, курсовая работа
Тьюринг высказал гипотезу (известную также как тезис Тьюринга) о том, что для всякой вычислимой функции может быть построена машина Тьюринга. Этот тезис также не может быть доказан, так как включает нестрогое понятие вычислимой функции.
Для всякой рекурсивной функции может быть построена машина Тьюринга и, обратно, всякая машина Тьюринга вычисляет рекурсивную функцию.
Целю данной курсовой работы, является рассмотрение достаточных условий разрешимости, проблемы остановки машин Тьюринга. Проанализировать алгоритмическую неразрешимость ряда задач.
Введение …………………………………………………….………….…… 3
Определение машины Тьюринга ……………………………….. …..…. 5
Работа машины Тьюринга …………………………………………..... 8
Способы задания машин Тьюринга, операции над ними ……….. …… 9
3.1. Формулировка проблемы остановки машины Тьюринга……..…. 11
. Проблема вычислимости машины Тьюринга ……….……..…….. 15
Множество граничных конфигураций. Достаточные условия
разрешимости проблемы остановки…………………………..……...... 16
Машины Тьюринга с двумя символами и
не более чем тремя состояниями …………………....……………..….. 19
Заключение …………………………………..…………………..………. .. 23
Список литературы ………………………………………………………... 24