Автор работы: Пользователь скрыл имя, 18 Декабря 2012 в 22:57, реферат
Машина Тьюринга - это очень простое вычислительное устройство. Она состоит из ленты бесконечной длины, разделенной на ячейки, и головки, которая перемещается вдоль ленты и способна читать и записывать символы. Также у машины Тьюринга есть такая характеристика, как состояние, которое может выражаться целым числом от нуля до некоторой максимальной величины. В зависимости от состояния машина Тьюринга может выполнить одно из трех действий: записать символ в ячейку, передвинуться на одну ячейку вправо или влево и установить внутреннее состояние.
Введение 2
1. Описание машины Тьюринга 3
1.1 Свойства машины Тьюринга как алгоритма 5
2. Сложность алгоритмов 7
2.1 Сложность проблем 9
3. Машина Тьюринга и алгоритмически неразрешимые проблемы 12
Заключение 16
Список литературы 18