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

Машина Тьюринга - это очень простое вычислительное устройство. Она состоит из ленты бесконечной длины, разделенной на ячейки, и головки, которая перемещается вдоль ленты и способна читать и записывать символы. Также у машины Тьюринга есть такая характеристика, как состояние, которое может выражаться целым числом от нуля до некоторой максимальной величины. В зависимости от состояния машина Тьюринга может выполнить одно из трех действий: записать символ в ячейку, передвинуться на одну ячейку вправо или влево и установить внутреннее состояние.

1.Введение…………………………………………………………………………2
2.Описание машины Тьюринга………………………………………………….
3.Свойства машины Тьюринга…………………………………………………..
4.Сложность алгоритмов…………………………………………………………
5.Сложность проблем…………………………………………………………….
6.Машина Тьюринга и алгоритмические неразрешимые проблемы………...
7.Заключение…………………………………………………………………....
8.Список литературы…………………………………………………………......