Машина Тьюринга - это интересно. Часть 2
В Части 1 я начал рассказ про то, почему машина Тьюринга - это интересно, и про то, что такое лента машины Тьюринга (бесконечная строка из клеток, в каждой из которых написаны 0 или 1). В этой части я завершу описание машины Тьюринга и предложу на выбор читателям несколько вариантов того, про что мне писать дальше.
Вначале расскажу о следующей важной детали: считывающей головке. Представьте, что вы поставили карандашик напротив какой-нибудь клеточки с числом, а потом взяли и сдвинули этот карандашик на одну клеточку, например, вправо. Потом взяли и сдвинули его еще на одну клеточку вправо, потом сдвинули ее влево, потом еще раз влево, еще раз и еще раз и так далее. Ну, вот, считывающая головка машины Тьюринга - это как такой карандашик, который может двигаться вдоль ленты. В каждый момент времени он находится напротив одной из клеточек ленты и может за один шаг сдвинуться еще на одну клеточку вправо или влево.
Но ведь карандашиком можно не просто водить туда-сюда: можно еще им и писать! Взять и написать в какой-нибудь клеточке нолик или единичку. Считывающая головка машины Тьюринга делает то же самое: может в любой клеточке написать нолик или единичку. Причем считывающая головка - не просто как карандашик, а как карандашик и стиралка: она может стереть цифру в клеточке, напротив которой она находится, и написать вместо нее другую.
Если смотреть на машину Тьюринга со стороны, то только это и увидишь: двигается считывающая головка вдоль ленты туда-сюда, стирает одни символы, рисует вместо них другие, потом опять стирает, опять рисует, опять двигается и т.д.
Но самое интересное не то, как выглядит машина Тьюринга снаружи, а то, что у нее внутри! Самое интересное: почему она движется иногда в одну сторону, а иногда - в другую; почему иногда стирает одни символы и пишет вместо них другие, а иногда - ничего не трогает и движется дальше?
И здесь мы переходим к следующему важному кусочку - состояниям машин Тьюринга. Состояние машины Тьюринга - это как режим работы у пылесоса, фена или любого другого прибора: в одном режиме пылесос втягивает пыль, в другом - выдувает; в одном режиме фен подает теплый воздух, в другом - очень теплый, в третьем - горячий. Состояния машин Тьюринга - это, по сути, такие же режимы работы, которые определяют, чем будет заниматься машина Тьюринга дальше, разница только в том, что у пылесоса два режима, у фена - три, а у машин Тьюринга таких состояний может быть любое конечное количество: одно, шесть, 100, 2543 - у каждой машины свое количество.
В зависимости от состояний считывающая головка будет вести себя по-разному: в одном состоянии она будет стирать цифры и менять их на другие, в другом - не будет, в одном состоянии она пойдет в одну сторону, в другом - в другую. Если смотреть на машину Тьюринга, то будет видна только считывающая головка, которая совершает какие-то действия, но в действительности в процессе этого движения состояния машины Тьюринга постоянно меняются.
Последняя деталь машины Тьюринга, про которую надо рассказать: это правила перехода (или программа Тьюринга), которым следует машина Тьюринга. Правила эти тоже очень простые, например, такое: "Если машина находится в состоянии А, а считывающая головка стоит напротив нуля, то перейди в состояние В, нарисуй вместо нуля единицу и сдвинь считывающую головку на одну клеточку вправо". Или, например, такое: "Если машина находится в состоянии А, а считывающая головка стоит напротив единицы, то останься в состоянии А, оставь единицу и сдвинь считывающую головку на одну клеточку вправо".
Вот и всё: описание машин Тьюринга - без формул и непонятных математических символов - закончено. Осталось только рассказать, как они начинают и заканчивают свою работу.
Работа машины Тьюринга начинается с того, что ей на вход подается лента с каким-то числом в виде соответствующего количества единиц (например, если на вход подано число 7 - то это лента, на которой подряд нарисованы семь единичек, а слева и справа от них стоят одни нули), считывающая головка находится около самой левой единицы, а сама машина находится в своем состоянии №1. Далее машина Тьюринга начинает свою работу в соответствии с правилами перехода: меняет состояния, двигает головку, стирает и пишет цифры. Работает, работает, а затем или через какое-то время останавливается или никогда не останавливается, работает вечно - такое тоже возможно. Если она остановилась, то на выход подается число, равное количеству единиц на ленте. Например, если после остановки машины Тьюринга лента имеет такой вид: 011100101010, то на выход подается число 6. Это значит, что данная машина Тьюринга, получив на входе число 7, выдала число 6 как результат своей работы.
Предлагаю читателям в комментариях выбрать, про что мне написать в Части 3:
1. Привести несколько простых примеров машин Тьюринга, чтобы было лучше понятно, что они умеют и зачем они нужны.
2. Рассказать про то, как и когда Алан Тьюринг придумал свои машины, и какое место они занимают в его творческом наследии.
3. Рассказать про то, как связаны машины Тьюринга и современные компьютеры.
4. Рассказать про роль машин Тьюринга в математике и компьютерных науках.