|
Раз мы не смотрим на машину Тьюринга как на конструкцию «в металле», мы должны описать схему ее работы таким способом, чтобы не возникало неоднозначностей в понимании и трудностей в ее анализе. Для этого надо задать программу тьюринговой машины, в которой будет указано, какие акты поведения соответствуют каждой возможной паре «обозреваемый знак – внутреннее состояние». Такая программа может строиться следующим образом. Поскольку внутренних состояний и типов знаков конечное число, мы можем выписать столбец всех пар «внутреннее состояние – знак». Число этих пар равно произведению числа внутренних состояний на число знаков алфавита, включая пустой знак. Против каждой из пар выпишем другую пару: обозначение того механического действия, которое должна произвести машина, и того (нового) внутреннего состояния, в которое она должна перейти. Возникший таким образом список четверок и будет программой некоторой машины Тьюринга. Опираясь на него, можно имитировать работу машины для каждой конфигурации на ленте. Пусть внешний алфавит состоит из пустого знака и вертикальной палочки |. В качестве «заменителя» пустого знака мы будем использовать знак X. Обозначим сдвиг ленты на одну ячейку влево (который можно трактовать и как сдвиг головки машины по ленте вправо) символом П; сдвиг ленты вправо (то есть движение головки по ленте влево) – символом Л; внутренние состояния обозначим через С1, С2, ..., Сk, причем С1 будет использоваться для исходного состояния, а Сk – для конечного, то есть такого, в котором машина оказывается после остановки (когда с ленты считывается результат ее работы). Условимся считать, что если машина не меняет символа, находящегося в обозреваемой ячейке, то она стирает его и затем записывает снова в той же ячейке (за один такт). Примем также, что в начале своей работы машина «нацелена» на самый левый знак, нанесенный на ее ленте. После этих соглашений можно приступить к рассмотрению конкретных машин Тьюринга. 1. Конфигурация на ленте представлена следующим расположением вертикальных палочек: ... X X X | | | | | ... | | | | | X X X ... (сплошной массив из произвольного конечного числа палочек, справа и слева от которого неограниченно простираются пустые ячейки). Программа машины состоит из единственной четверки (команды программы): С1 | | Сk (четверки, до которых при переработке заданной конфигурации дело заведомо дойти не может, обычно не выписывают). Вначале машина нацелена на самую левую палочку. Внутреннее состояние машины в начальный момент есть С1 поэтому данная четверка как раз и дает информацию о действии машины. Как видно из структуры четверки, машина должна стереть единицу и вновь ее восстановить, а затем перейти в состояние Сk, то есть остановиться. Понятно, что конфигурация, написанная на ленте, при этом не изменится; это верно для любого количества палочек. Это – пример «тождественной» машины Тьюринга. — 98 —
|