Зырить аржан for Вычисления на машинах Тьюринга

{{YouTube|b7QODdb_tVw|width=300|height=250}}

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

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

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

== Практическое применение ==
Несмотря на то что в период первоначального исследования подобных моделей программы разрабатывались аналитически и записывались исключительно на бумаге, в настоящее время данные теоретические концепции активно используются в прикладной алгоритмике с применением вычислительной техники. Разработаны разнообразные программные эмуляторы, позволяющие на практике реализовывать и тестировать алгоритмы. Подобные программные комплексы предоставляют интерфейс, визуализирующий бесконечную ленту и перемещения каретки. Это дает возможность разрабатывать алгоритмы, запускать их пошаговое выполнение и верифицировать корректность написанных инструкций путем наблюдения за реальным изменением данных на эмулируемой ленте.

== Особенности и характеристики ==
Рабочий алфавит машины Тьюринга классически может состоять из бинарных символов, что позволяет интерпретировать записанные на ленте слова как числовые значения. Замещение одних символов другими в процессе работы головки фактически является реализацией арифметических или логических операций над числами. Важной структурной особенностью машин Тьюринга является многообразие способов задания управляющей логики. Программа может быть описана не только в виде текстовой таблицы команд, связывающих текущее состояние, считываемый символ и необходимое действие, но и в графическом виде. Поскольку устройство функционирует по принципам конечного автомата, его программа легко отображается с помощью ориентированного графа или диаграммы переходов, что значительно упрощает анализ логики работы модели.

== См. также ==

[[Грамматики]]

[[Category:Теория автоматов и алгоритмов]]

[https://www.youtube.com/watch?v=b7QODdb_tVw Смотреть видео]