Тьюринга Машина

Название, закрепившееся за вычислительными машинами абстрактными нек-рого точно охарактеризованного типа. Концепция такого рода машины возникла в середине 30-х гг. 20 в. у А. М. Тьюринга [1] в результате произведенного им анализа действий человека, выполняющего в соответствии с заранее разработанным планом те или иные вычисления, т. е. последовательные преобразования знаковых комплексов. Анализ этот, в свою очередь, был осуществлен им с целью решения назревшей к тому времени проблемы поиска точного математич. эквивалента для общего интуитивного представления об алгоритме. Входе развития алгоритмов теории появился ряд модификаций первоначального тьюринговского определения. Здесь дается версия, восходящая к Э. Посту [2],- в таком виде определение Т. м. получило весьма большое распространение (детально Т. м. описаны, напр., в [3] и [4]). Т. м. удобно представлять себе в виде автоматически функционирующего устройства, способного находиться в конечном числе внутренних состояний и снабженного бесконечной внешней памятью — лентой. Среди состояний имеется два выделенных — начальное и заключительное. Лента разделена на клетки и неограниченна влево и вправо. В каждой клетке ленты может быть записана любая из букв нек-рого алфавита А (ради единообразия удобно считать, что в пустой клетке записана лпустая буква