Реферат: Алгоритмические машины

− i ≠ j ≠ 0 – соответствует замене одного знака другим.

Таким образом, в машине Тьюринга реализуется система предельно простых команд обработки информации. Эта система команд обработки дополняется также предельно простой системой команд перемещений ленты: на ячейку влево, на ячейку вправо и остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным. Однако, хотя фактически происходит перемещение ленты, обычно рассматривается сдвиг головки относительно обозреваемой секции. По этой причине команда сдвига ленты влево обозначается R (Right), сдвига вправо – L (Left), отсутствие сдвига – S (Stop). Мы будем говорить именно о сдвиге головки и считать R, L и S командами ее движения. Элементарность этих команд означает, что при необходимости обращения к содержимому некоторой ячейки, она отыскивается только посредством цепочки отдельных сдвигов на одну ячейку. Разумеется, это значительно удлиняет процесс обработки, зато позволяет обойтись без нумерации ячеек и использования команд перехода по адресу, т.е. сокращает количество истинно элементарных шагов, что важно в теоретическом отношении.

Обработка информации и выдача команд на запись знака, а также сдвига ленты в машине Тьюринга производится логическим устройством (ЛУ). ЛУ может находиться в одном из состояний, которые образуют конечное множество и обозначаются Q ={q₁ …q_m , z} , причем состояние z соответствует завершению работы, а q₁ является начальным (исходным). Q совместно со знаками R, L, S образуют внутренний алфавит машины. ЛУ имеет два входных канала (a_i , q_i ) и три выходных (a_i+1 , q_i+1 , D_i+1 ) (см. рис. 2):

Рис. 2 - Схема логического устройства машины Тьюринга

Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (a_i ,), а на другой вход – знак, обозначающий состояние ЛУ в данный момент (q_i ). В зависимости от полученного сочетания знаков (a_i , q_i ) и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (a_i+1 ), подает команду перемещения головки (D_i+1 из R, L и S), а также дает команду на вызов следующего управляющего знака (q_i+1 ). Таким образом, элементарный шаг (такт) работы машины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стер?