МАШИНА ТЬЮРИНГА

МАШИНА ТЬЮРИНГА (Turing machine). Получила свое название по имени английского математика Алана Тьюринга, предложившего в 1937 г. способ формального задания алгоритмов с помощью некоторой абстрактной машины. Суть работы М. Т. сводится к следующему. Имеется потенциально бесконечная лента, разбитая на ячейки, в каждой из которых может быть записан один символ из некоторого конечного алфавита. М. Т. имеет головку чтения/записи, которая позволяет прочитать символ в текущей ячейке, записать символ в ячейку, а также сдвинуть головку в соседнюю ячейку(влево или вправо). Машина работает дискретно, по тактам и на каждом такте находится в одном из возможных состояний, которых конечное число. ||Для каждой пары (состояние, обозреваемый символ) определена тройка ||(записываемый символ, движение головки, новое состояние). До начала paботы М. Т. находится в начальном состоянии, а головка чтениязаписи обозревает на ленте самую левую непустую ячейку. Таким образом, обозревая очередной символ, М. Т. записывает новый символ (может быть, тот же caмый), сдвигает головку влево, вправо или остается на месте и переходит в(новое состояние или остается в прежнем.