Turing machine

Turing machine – машина Тьюринга гипотетический вычислитель, предложенный английским математиком Аланом Тьюрингом (Alan Turing) в 1936 г. как инструмент для изучения сложности алгоритмов. Состоит из блока управления, считывающей и записывающей головки и бесконечной длины ленты с ячейками, каждая из которых может содержать произвольный символ некоторого конечного алфавита. Вычисления состоят из последовательности шагов, задаваемых программой блоку управления. Ячейка, находящаяся под считывающей головкой называется текущей. Каждый шаг включает считывание символа в текущей ячейке, запись символа в неё, возможное перемещение головки в соседнюю ячейку слева или справа. Вычисления начинаются в специальном состоянии, называемом стартовым, и заканчивается в состоянии, называемом остановом. Кроме наличия бесконечной памяти, современные процессоры очень похожи на машину Тьюринга (см. также abstract computer).