Машина BMW? Mercedes? НЕТ! Тьюринга

Машина Тьюринга, сокращенно МТ, это как абстрактный исполнитель или абстрактная вычислительная машина, которую Алан Тьюринг предложил в 1936 году для формализации понятия алгоритма. Ee можно рассматривать как расширение обычного конечного автомата. Согласно тезису Чёрча — Тьюринга, Машина Тьюринга способна имитировать работу любых других вычислителей, задавая правила для переходов состояний. Эти другие вычислители могут выполнять вычисления пошагово, где каждый шаг достаточно прост и элементарен.
Иными словами, любой интуитивный алгоритм можно реализовать с помощью машины Тьюринга.

• Алан Тьюринг  -  английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики. Офицер ордена Британской империи (OBE, 1945), член Лондонского королевского общества (1951) .
• Конечный автомат - модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. Является частным случаем абстрактного дискретного автомата, число возможных внутренних состояний которого конечно.

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

• Теория сложности алгоритмов - изучает степень сложности алгоритмов в решении задач с использованием формально определенных моделей вычислительных устройств. Эта наука определяет необходимые ресурсы, такие как время и память, для выполнения алгоритмов. Иногда также анализируется другие виды сложности, например, физические параметры, такие как размеры микросхем или количество процессоров, необходимых для параллельных алгоритмов. 

Как устроена машина?

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

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

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

Как она работает?

Конкретная машина Тьюринга задаётся перечислением букв алфавита A, множеством состояний Q и набором правил перехода, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать начальное и конечное состояния, начальную конфигурацию на ленте и расположение головки машины. 

Пример машины Тьюринга для умножения чисел в унарной системе счисления. Запись правила перехода «qiaj→qi1aj1R/L/N» следует понимать так: qi — состояние, при котором выполняется это правило, aj — данные в ячейке, в которой находится головка, qi1 — состояние, в которое нужно перейти, aj1 — что нужно записать в ячейку, R/L/N — команда на перемещение.   

Чайник

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

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

Давно было доказано, что алгоритм, который можно реализовать на машине А, можно реализовать и на машине В, если эту машину А можно имитировать на машине В. 

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

На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу.

Есть программы для компьютеров, имитирующие работу машины Тьюринга. Но данная имитация неполная, так как в машине Тьюринга присутствует абстрактная бесконечная лента. Бесконечную ленту с данными невозможно в полной мере имитировать на компьютере с конечной памятью: суммарная память компьютера — оперативная память, жёсткие диски, различные внешние носители данных, регистры и кэш процессора и др. - может быть очень большой, но тем не менее всегда конечна.