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