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

КТО? Машина Тьюринга – математическая (воображаемая) машина, а не машина физическая. Она такой же математический объект, как функция, производная, интеграл и т.д. ЧТО? А́лан Ма́тисон Тью́ринг английский математик, логик, криптограф. В 1937 году предложил уточнение понятия алгоритма как процесса, который может совершаться специальной машиной, названной в дальнейшем машиной Тьюринга. Понятие «машина Тьюринга» было сформулировано за 9 лет до появления первой ЭВМ.

Устройство машины Тьюринга Лента Читающая головка Внутреннее состояние Считываемый символ Лента: Потенциально бесконечная; В одной ячейке – один символ; Пустая ячейка заполнена символом a 0. Головка: В каждый момент времени находится только в одном внутреннем состоянии; Начальное состояние – q 1 ; Конечное состояние – q 0.

1) Изменить / не изменить символ, записанный на ленте Действия машины Тьюринга 2) Изменить / не изменить своё внутреннее состояние 3) Переместить головку по ленте влево / вправо / не перемещать головку За один такт своей работы машина Тьюринга может:

Ещё немного определений Конфигурация: Машина: Программа – совокупность всех команд машины.

Пример машины Тьюринга QA QA q1q1 q2q2 q3q3 0q 1 0Lq 3 1Rq 1 0L 1q 2 0Lq 2 1Lq 3 1R q00q00q 2 Lq 3 R Рассмотрим работы машины Тьюринга, имеющую следующую программу: q q q q q q q q q q q q q q q q q q q q … … … T f(a,b) = a + b

Зачем? Тезис Тьюринга: Для нахождения значений функции тогда и только тогда существует какой-нибудь алгоритм когда существует машина Тьюринга, вычисляющая данную функцию. Данный тезис не может быть строго доказан методами математики, однако до сих пор не удалось придумать вычислимую функцию, которую нельзя было бы запрограммировать в виде машины Тьюринга. Выводы: Машина Тьюринга – математически строгий аналог понятия «алгоритм». Принцип работы машины Тьюринга лежит в основе всех современных ЭВМ.