23 июня 1912 года родился Алан Тьюринг – английский математик, логик, криптограф. Он внес большой вклад в развитие информатики, в его честь названа самая престижная в мире награда в области информатики – Премия Тьюринга. Во время Второй мировой Тьюринг активно занимался криптоанализом, в том числе криптоанализом немецкого шифратора Enigma (на портале Эрудит.Онлайн есть конкурс по криптографии «Энигма»).
В этой статье остановимся подробнее на машине Тьюринга и попытаемся объяснить ее работу максимально простым языком.
Машина Тьюринга
Машина Тьюринга – это абстрактная вычислительная машина. Если совсем просто, то машина Тьюринга – это воображаемый компьютер с бесконечной памятью.
Формально машина состоит из бесконечной ленты и управляющего устройства, которое может считывать и записывать символы в ячейки ленты. Управляющее устройство может двигаться влево и вправо по ленте.
Для чего это нужно?
Тьюринг предложил эту модель для формализации понятия алгоритма. То есть считается, что задачу можно решить с помощью некоторого алгоритма тогда и только тогда, когда ее решение можно представить в виде программы для машины Тьюринга (эта гипотеза называется тезисом Чёрча — Тьюринга).
Так как устройство машины довольно простое, то, очевидно, что каждый шаг в такой программе должен быть элементарен.
Как работает машина Тьюринга?
Шаг машины можно представить так:
- Управляющее устройство, указывающее на конкретную ячейку на ленте, считывает значение в этой ячейке.
- По правилам, которые заданы заранее для решения задачи, управляющее устройство может изменить символ в ячейке (а может и не менять), а затем остаться на месте или сдвинуться на соседнюю ячейку вправо или влево. Также может измениться состояние управляющего устройства (а может и остаться прежним).
У управляющего устройства есть отдельный параметр, который называется состоянием. Набор таких состояний задается для каждой конкретной программы свой, но обязательно в этом наборе есть начальное состояние (в котором машина начинает работать) и конечные состояния (когда мы считаем, что программа завершилась, и машина останавливается). Эти состояния меняются в соответствии с правилами, которые заранее заданы.
Как записать простейшую программу?
Рассмотрим очень простую задачу. Пусть у нас есть последовательность из 0 и 1, и мы хотим в ней заменить все символы 0 на @. Как может выглядеть программа для машины Тьюринга в этом случае?
Программа задается набором правил, которые еще называют правилами перехода. Для записи этих правил нет какого-то единого языка, поэтому в нашей статье запишем их в виде таблицы.
Итак, в качестве входных данных у нас есть последовательность символов 0 и 1, и мы будем называть ее входным словом. Для простоты мы будем считать, что управляющее устройство указывает на первый слева символ нашего слова (если управляющее устройство указывает на произвольный символ слова, то эта проблема легко решается, но сейчас пропустим этот момент).
Наш набор правил:
А теперь разберемся, что все это означает.
- q1, q0 – это состояния нашего управляющего устройства. В данном случае их всего 2, и q1 – это начальное состояние, а q0 – конечное. Множество состояний, а также то, какое из них является начальным, а какие – конечными, все это должно быть задано в условиях задачи.
- Символы, которые могут быть записаны в ячейках, еще называют внешним алфавитом. И в нашем примере во внешнем алфавите 4 символа: «0», «1», «@» и символ s0. s0 – это такой особый символ, который означает «пустую» ячейку на ленте. То есть он показывает нам, что входное слово закончилось. В примере мы его обозначили через s0, но это не является универсальным обозначением «пустого» символа, поэтому в условиях задачи должно быть отдельно указано, как именно обозначается этот символ.
- Как, вероятно, все уже догадались, символ «→» означает сдвиг на одну ячейку вправо. В нашем примере используется только одна эта команда перемещения управляющего устройства, а всего их может быть три – влево, вправо и остаться на месте. Иногда их обозначают стрелками, как сделали мы, иногда буквами (например, английскими R, L, N, где N означает «остаться на месте»).
- Перейдем к самим правилам.
В желтой ячейке таблицы записано правило «@ →». Это означает, что если в текущей ячейке ленты записан символ 0, то машина заменяет его на @, а затем сдвигается на одну ячейку вправо. Состояние при этом не меняется.
В зеленой ячейке таблицы записано правило «→». Это означает, что если в текущей ячейке ленты записан символ 1, то машина его не меняет, а просто сдвигается на одну ячейку вправо. Состояние при этом не меняется.
Следующая ячейка во второй строке таблицы пустая. Это означает, что у нас нет правила для ситуации, когда машина, находясь в состоянии q1, видит символ @ в ячейке ленты. В нашей задаче предполагается, что на вход подается последовательность, состоящая только из 0 и 1. Как вы думаете, что будет, если во входном слове допустить ошибку и добавить символ @? Как можно решить эту проблему?
В голубой ячейке таблицы записано правило «q0». Это означает, что, увидев символ пустой ячейки, машина переходит в состояние q0 – конечное состояние. То есть программа завершила свою работу.
Пример работы программы
Пусть у нас есть входное слово 01011100, и мы хотим проверить, как будет работать машина. Подчеркнутый символ будет означать то, на какую позицию сейчас указывает управляющее устройство.
На 9м шаге машина, находясь в состоянии q1, видит символ s0. По правилу она переходит в состояние q0 и останавливается. Входное слово «01011100» превратилось в слово «@1@111@@».
Существуют программы для обычных компьютеров, которые имитируют работу машины Тьюринга, но это неполная имитация, т.к. все компьютеры обладают конечной памятью, а в машине Тьюринга лента с данными бесконечна.
На Эрудит.Онлайн подготовлен материал, где можно проверить, насколько хорошо вы разобрались в теме, а также посмотреть несколько примеров программ: конкурс «Машина Тьюринга».
