🌀 Каждому программисту хоть раз встречался термин «Машина Тьюринга». Рассказываем что это такое и как работает.

В 30-е годы XX века английский математик Алан Тьюринг придумал абстрактную вычислительную машину для решения проблемы математической логики.

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

😵‍💫 Из чего состоит машина?

• бесконечная лента с ячейками
• автомат или головка для чтения и записи (управляющее устройство)
• программа

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

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

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

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