Алгоритмические машины (стр. 4 из 6)
Целое число k записывается на ленте машины Поста посредством k+1 следующих подряд отмеченных секций, т.е. применяется унарная система счисления. Соседние записи чисел на ленте разделяются одной или несколькими пустыми секциями.
Ниже приведен пример записи чисел 0, 2 и 3.
| M | M | M | M | M | M | M | M |
Круг вычислительных задач, решаемых с помощью машины Поста, весьма широк. Однако, как указывалось выше, на уровне элементарных шагов все сводится к постановке или удалению метки и сдвигу головки. В качестве примеров рассмотрим несколько задач, традиционно обсуждаемых при освоении машины Поста. Поскольку вид программы (последовательности команд машины) зависит от начального состояния машины, оно должно быть в явном виде указано в постановке задачи.
4. Алгоритмическая машина Тьюринга
Машина Тьюринга (Turing machine) получила свое название по имени английского математика Алана Тьюринга, предложившего в 1937 г. способ формального задания алгоритмов с помощью некоторой абстрактной машины. Суть работы сводится к следующему. Имеется потенциально бесконечная лента, разбитая на ячейки, в каждой из которых может быть записан один символ из некоторого конечного алфавита. Машина Тьюринга имеет головку чтения/записи, которая позволяет прочитать символ в текущей ячейке, записать символ в ячейку, а также сдвинуть головку влево или вправо в соседнюю ячейку. Машина работает дискретно, по тактам и на каждом такте находится в одном из возможных состояний, которых конечное число. Для каждой пары (состояние, обозреваемый символ) определена тройка (записываемый символ, движение головки, новое состояние). До начала работы машина Тьюринга находится в начальном состоянии, а головка чтения-записи обозревает на ленте самую левую непустую ячейку. Таким образом, обозревая очередной символ, машина записывает новый символ (может быть, тот же самый), сдвигает головку влево, вправо или остается на месте и переходит в новое состояние или остается в прежнем.
Машина Тьюринга состоит из трех частей: ленты, считывающей (записывающей) головки и логического устройства (рис. 1).
Лента выступает в качестве внешней памяти. Она считается неограниченной (бесконечной). Уже это свидетельствует о том, что машина Тьюринга является модельным устройством, поскольку ни одно реальное устройство не может обладать памятью бесконечного размера.
Рис. 1 - Схема машина Тьюринга
Как и в машине Поста, лента разбита на отдельные ячейки, однако в машине Тьюринга неподвижной является головка, а лента передвигается относительно нее вправо или влево.
Другим отличием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите A = {Δ, a1…an} – этот алфавит называется внешним. В нем выделяется специальный символ – Δ, называемый пустым знаком – его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.
Головка всегда расположена над одной из ячеек ленты. Работа происходит тактами (шагами). Система исполняемых головкой команд предельно проста: на каждом такте она производит замену знака в обозреваемой ячейке ai знаком aj. При этом возможны сочетания:
− j = i – означает, что в обозреваемой ячейке знак не изменился;
− i ≠ 0, j = 0 – хранившийся в ячейке знак заменяется пустым, т.е. стирается;
− i = 0, j ≠ 0 – пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака;
− i ≠ j ≠ 0 – соответствует замене одного знака другим.
Таким образом, в машине Тьюринга реализуется система предельно простых команд обработки информации. Эта система команд обработки дополняется также предельно простой системой команд перемещений ленты: на ячейку влево, на ячейку вправо и остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным. Однако, хотя фактически происходит перемещение ленты, обычно рассматривается сдвиг головки относительно обозреваемой секции. По этой причине команда сдвига ленты влево обозначается R (Right), сдвига вправо – L (Left), отсутствие сдвига – S (Stop). Мы будем говорить именно о сдвиге головки и считать R, L и S командами ее движения. Элементарность этих команд означает, что при необходимости обращения к содержимому некоторой ячейки, она отыскивается только посредством цепочки отдельных сдвигов на одну ячейку. Разумеется, это значительно удлиняет процесс обработки, зато позволяет обойтись без нумерации ячеек и использования команд перехода по адресу, т.е. сокращает количество истинно элементарных шагов, что важно в теоретическом отношении.
Обработка информации и выдача команд на запись знака, а также сдвига ленты в машине Тьюринга производится логическим устройством (ЛУ). ЛУ может находиться в одном из состояний, которые образуют конечное множество и обозначаются Q ={q1…qm, z} , причем состояние z соответствует завершению работы, а q1 является начальным (исходным). Q совместно со знаками R, L, S образуют внутренний алфавит машины. ЛУ имеет два входных канала (ai, qi) и три выходных (ai+1, qi+1, Di+1) (см. рис. 2):
Рис. 2 - Схема логического устройства машины Тьюринга
Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (ai,), а на другой вход – знак, обозначающий состояние ЛУ в данный момент (qi). В зависимости от полученного сочетания знаков (ai, qi) и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (ai+1), подает команду перемещения головки (Di+1 из R, L и S), а также дает команду на вызов следующего управляющего знака (qi+1). Таким образом, элементарный шаг (такт) работы машины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние. Схема функционирования такой машины представлена на рисунке 3.
Рис. 3 - Схема функционирования машины Тьюринга
алгоритмический машина пост тьюринг
В данной схеме отражено разделение памяти на внешнюю и внутреннюю. Внешняя представлена, как указывалось, в виде бесконечной ленты – она предназначена для хранения информации, закодированной в символах внешнего алфавита. Внутренняя память представлена двумя ячейками для хранения следующей команды в течение текущего такта: в Q передается из ЛУ и сохраняется следующее состояние (qi+1), а в D – команда сдвига (Di+1). Из Q по линии обратной связи qi+1 поступает в ЛУ, а из D команда поступает на исполнительный механизм, осуществляющий при необходимости перемещение ленты на одну позицию вправо или влево.
Общее правило, по которому работает машина Тьюринга, можно представить следующей записью: qi aj → qi’ aj’ Dk, т.е. после обзора символа aj головкой в состоянии qi в ячейку записывается символ aj’, головка переходит в состояние qi’, а лента совершает движение Dk. Для каждой комбинации qi aj имеется ровно одно правило преобразования (правил нет только для z, поскольку, попав в это состояние, машина останавливается). Это означает, что логический блок реализует функцию, сопоставляющую каждой паре входных сигналов qi aj одну и только одну тройку выходных qi’aj’Dk – она называется логической функцией машины и обычно представляется в виде таблицы (функциональной схемой машины), столбцы которой обозначаются символами состояний, а строки – знаками внешнего алфавита. Если знаков внешнего алфавита n, а число состояний ЛУ m, то, очевидно, общее число правил преобразования составит n×m.
Конкретная машина Тьюринга задается перечислением элементов множеств A и Q, а также логической функцией, которую реализует ЛУ, т.е. набором правил преобразования. Ясно, что различных множеств A, Q и логических функций может быть бесконечно много, т.е. и машин Тьюринга также бесконечно много.
Прежде чем обсуждать функционирование машины Тьюринга, введем еще одно понятие — конфигурации машин, т.е. совокупности состояний всех ячеек ленты, состояния ЛУ и положение головки.
Записать конфигурацию можно следующим образом: Δa1 qi aj…ak Δ, которая означает, что в слове из k символов обозревается секция номер j и при этом управляющее устройство находится в состоянии qi. Ясно, что конфигурация машины может содержать любое количество символов внешнего алфавита и лишь один символ внутреннего. Часто конфигурацию записывают в виде a1 qi a2, где a1 – слово на ленте слева от головки, a2 – слово на ленте справа от головки, включая обозреваемый знак. Слева от a1 и справа от a2 лента пуста.
Перед началом работы на пустую ленту записывается исходное слово a конечной длины в алфавите A; головка устанавливается над первым символом слова a, ЛУ переводится в состояние q1 (т.е. начальная конфигурация имеет вид q1a). Поскольку в каждой конфигурации реализуется только одно правило преобразования, начальная конфигурация однозначно определяет всю последующую работу машины, т.е. всю последовательность конфигураций вплоть до прекращения работы.