Атырауский инженерно-гуманитарный институт Машина Тьюринга Подготовил: студент

Алтынбек
Проверила: старший преподаватель Кубашева Динара
Атырау-2018

Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением модели конечного автомата и, согласно тезису

Чёрча — Тьюринга, способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.

на ячейки, и управляющее устройство с конечным числом состояний.
Управляющее устройство может перемещаться

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

в таблице соответствует не более одного правила, и недетерминированной в противном случае.
Итак,

машина Тьюринга — математическая абстракция, умозрительное построение человеческого разума: в природе её нет. Или есть? Сразу приходит на ум, как работает живая клетка. Хотя бы два примера.
Для производства белков в клетке с помощью сложно устроенного фермента — РНК-полимеразы — считывается информация с ДНК, своего рода информационной ленты машины Тьюринга.
Ещё более похож на машину Тьюринга процесс исправления ошибок в ДНК — её репарация. Здесь ДНК-полимераза вместе с другими белками двигается по ленте ДНК и считывает обе её половинки (геномная ДНК, как известно, представляет собой две переплетенных нити, несущих одну и ту же информацию). Если информация в половинках не совпадает, ДНК-полимераза принимает одну из них за образец и «правит» другую.

от его текущего состояния и входных данных, при условии что общее

возможное количество состояний конечно. Конечный автомат является частным случаем абстрактного автомата. Конечный автомат может быть детерминированным или недетерминированным, в зависимости от того, имеется ли один или несколько вариантов его поведения на каком-то шаге.

и в каждый момент времени находящегося в одном состоянии из множества возможных.

На вход этому устройству поступают символы одного языка, на выходе оно выдаёт символы (в общем случае) другого языка.

английский математик, логик, криптограф, изобретатель Машины Тьюринга.
В самой статье больше

про труды Тьюринга: помимо текста про машину Тьюринга, который мы еще приведем дальше, повествуется о том, что он работал над "проблемой зависания" (Забавно, не так ли? Компьютеров еще не было, и системы Windows тоже, а проблема зависания уже была.); героическая история про то, как Тьюринг взломал код "Энигмы" во время Второй Мировой Войны и тем самым спас Великобританию; факт о том, что он является основателем теории искуственного интеллекта, а также упоминание о знаменитом тесте Тьюринга. Сейчас этот тест уже не так часто используется как завязка научно-фантастического рассказа, однако проблема человеческого в машине всегда останется классикой, как и романы Айзека Азимова и Станислава Лема.

переход одновременно в несколько (константа) состояний — можно считать, что

происходит «клонирование» машины (состояние, содержимое лент, положение головок).
Таким образом, для каждого массива входных данных имеется не один, а несколько (в общем случае — экспоненциальное число) путей, по которым может развиваться вычисление.
Недетерминированная машина Тьюринга выдаст ответ 1, если существует хотя бы один путь развития вычисления, на котором выдается ответ 1, и 0 — в противном случае (таким образом, ответы «ДА» и «НЕТ» в случае недетерминированных вычислений несимметричны).
Класс алгоритмов, выполняемых за полиномиальное время на недетерминированных машинах Тьюринга, называется классом NP.

и значений на ленте машина может совершить один из нескольких

(можно считать, без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки).
Вероятностная Машина Тьюринга похожа на недетерминированную машину Тьюринга, только вместо недетерминированного перехода машина выбирает один из вариантов с некоторой вероятностью.
Существует также альтернативное определение:
Вероятностная машина Тьюринга представляет собой детерминированную машину Тьюринга, имеющую дополнительно аппаратный источник случайных битов, любое число которых, например, она может «заказать» и «загрузить» на отдельную ленту и потом использовать в вычислениях обычным для МТ образом.
Класс алгоритмов, завершающихся за полиномиальное время на вероятностной машине Тьюринга и возвращающих ответ с ошибкой менее 1/3, называется классом BPP.