Что такое машина Тьюринга
Машина Тьюринга (МТ) - одна из фундаментальных моделей вычислений, предложенная в 1936 году английским математиком Аланом Тьюрингом. Наш интерактивный эмулятор позволяет пошагово проследить выполнение алгоритма и движение каретки по ленте памяти. По вычислительной мощности МТ эквивалентна нормальному алгоритму Маркова и лежит в основе современной теории алгоритмов.
История создания:
Тьюринг разработал свою модель, чтобы строго математически описать понятие "алгоритм" и ответить на вопрос, всякую ли математическую задачу можно решить автоматически. Его работа стала фундаментом всей теории вычислений и архитектуры современных компьютеров.
Как это работает?
Машина Тьюринга состоит из бесконечной ленты, головки и управляющего устройства. На каждом шаге она считывает символ под головкой и в зависимости от текущего состояния и этого символа выполняет действие: записывает новый символ, сдвигает головку влево или вправо, переходит в новое состояние. При достижении конечного состояния машина останавливается.
Где это применяется:
- Теория алгоритмов - помогает математически доказать, какие задачи в принципе можно решить на компьютере, а какие - нет.
- Оценка сложности - МТ служит идеальным эталоном: время работы алгоритма измеряется в шагах каретки, а затраченная память - в ячейках ленты.
- Криптография - доказательство надежности современных шифров опирается на то, что для их взлома любой МТ потребуется нереально много шагов.
Идеи Тьюринга 1936 года легли в основу всей современной информатики и компьютерной науки.