Введение

В теории вычислений система тегов — это детерминированная модель вычислений, опубликованная Эмилем Леоном Постом в 1943 году как простая форма канонической системы Поста. Систему тегов также можно рассматривать как абстрактную машину, называемую Post tag machine (не путать с машинами Поста-Тьюринга) — кратко, конечный автомат, единственная лента которого представляет собой очередь FIFO неограниченной длины, при этом на каждом переходе машина считывает символ в начале очереди, удаляет фиксированное количество символов из начала и добавляет к концу символьную строку, зависящую исключительно от первого считанного в этом переходе символа. Поскольку все указанные операции выполняются за один переход, машина тегов строго имеет только одно состояние.

Полнота Тьюринга систем m-tag

Для каждого m > 1 множество систем с m тегами является Тьюринг-полным; то есть, для каждого m > 1, для любой заданной машины Тьюринга T существует система с m тегами, которая эмулирует T. В частности, систему с 2 тегами можно построить для эмуляции универсальной машины Тьюринга, как это было сделано и . Обратно, машину Тьюринга можно показать как универсальную, доказав, что она может эмулировать Тьюринг-полный класс систем с m тегами. Например, доказал универсальность класса систем с 2 тегами с алфавитом {a1, , an, } и соответствующими продукциями {ananW1, , ananWn 1, anan, }, где Wk – это непустые слова; затем он доказал универсальность очень маленькой (4 состояния, 6 символов) машины Тьюринга, показав, что она может симулировать этот класс систем с тегами. Система с 2 тегами является эффективным симулятором универсальных машин Тьюринга за время . То есть, если – это детерминированная одноленточная машина Тьюринга, работающая за время , то существует система с 2 тегами, которая симулирует её за время .

Происхождение названия "tag"

Согласно сноске в [название работы], Б. П. Гилл предложил название для более раннего варианта задачи, в котором первые m символов остаются без изменений, а вместо этого отметка, указывающая текущую позицию, сдвигается вправо на m символов на каждом шагу. Задача определения, достигнет ли эта отметка конца последовательности, была названа "проблемой догонялок", по аналогии с детской игрой в догонялки.

Системы циклических меток

Циклическая система меток является модификацией исходной системы меток. Алфавит состоит только из двух символов, 0 и 1, а правила вывода представляют собой список правил, рассматриваемых последовательно, с возвратом к началу списка после рассмотрения последнего правила в списке. Для каждого правила проверяется самый левый символ слова: если символ равен 1, текущее правило добавляется к правому концу слова; если символ равен 0, символы к слову не добавляются; в любом случае, самый левый символ затем удаляется. Система останавливается, когда слово становится пустым.

Эмуляция систем меток с помощью систем циклических меток

Система m тегов с алфавитом {a1, …, an} и соответствующими продукциями {P1, …, Pn} эмулируется циклической системой тегов с m*n продукциями (Q1, …, Qn, …, …, …), где все, кроме первых n продукций, являются пустой строкой (обозначаемой ''). Qk – это кодировки соответствующих Pk, полученные путем замены каждого символа алфавита системы тегов двоичной строкой длиной n следующим образом (это применяется также к исходному слову вычисления системы тегов):

a1 = 100 00
a2 = 010 00
…
an = 000 01

То есть, ak кодируется двоичной строкой, в которой a находится на k-й позиции слева, а остальные символы – нули. Последовательные строки вычислений системы тегов затем будут представлены в виде каждой (m*n)-й строки эмуляции циклической системой тегов.