Машина Тьюринга

Устройство машины Тьюринга чрезвычайно просто, однако на ней можно выполнить практически любую программу. Для выполнения всех этих действий предусмотрена специальная таблица правил, в которой прописано, что нужно делать при различных комбинациях текущих состояний и символов, прочитанных с ленты.
В 1947 г. Алан Тьюринг расширил определение, описав "универсальную машину Тьюринга". Позже для решения определенных классов задач была введена ее разновидность, которая позволяла выполнять не одну задачу, а несколько.

Введение 2
1. Описание машины Тьюринга 3
1.1 Свойства машины Тьюринга как алгоритма 5
2. Сложность алгоритмов 7
2.1 Сложность проблем 9
3. Машина Тьюринга и алгоритмически неразрешимые проблемы 12
Заключение 16
Список литературы 18