В теории вычислений система тегов — это детерминированная модель вычислений, опубликованная Эмилем Леоном Постом в 1943 году как простая форма канонической системы Поста . [1] Систему тегов также можно рассматривать как абстрактную машину, называемую машиной тегов Поста (не путать с машинами Пост-Тьюринга ) — кратко, конечную машину , единственной лентой которой является очередь FIFO неограниченной длины. так, что при каждом переходе машина считывает символ в начале очереди, удаляет постоянное количество символов из головы и добавляет в хвост строку символов, которая зависит исключительно от первого символа, прочитанного в этом переходе.
Поскольку все указанные операции выполняются за один переход, машина тегов строго имеет только одно состояние.
Система тегов представляет собой тройку ( m , A , P ), где
Остановочное слово — это слово, которое либо начинается с символа остановки, либо имеет длину меньше m .
Преобразование t (называемое операцией тега ) определяется на множестве не прерывающихся слов, так что если x обозначает самый левый символ слова S , то t ( S ) является результатом удаления самых левых m символов слова S и добавив слово P(x) справа. Таким образом, система обрабатывает заголовок m-символа в хвост переменной длины, но формируемый хвост зависит исключительно от первого символа головы.
Вычисление с помощью системы тегов представляет собой конечную последовательность слов , созданную путем итерации преобразования t , начиная с первоначально заданного слова и заканчивая созданием останавливающего слова. (Согласно этому определению, вычисление не считается существующим, если за конечное число итераций не создано останавливающее слово. Альтернативные определения позволяют выполнять вычисления без остановки, например, используя специальное подмножество алфавита для идентификации слов, которые кодируют выходные данные.)
Термин «система m-тегов» часто используется, чтобы подчеркнуть номер удаления. Определения несколько различаются в литературе (см. Библиотеку), здесь представлено определение Рогожина. [2]
Использование символа остановки в приведенном выше определении позволяет кодировать выходные данные вычислений только в последнем слове, тогда как в противном случае выходные данные будут кодироваться во всей последовательности слов, полученной в результате итерации операции тега.
Общее альтернативное определение не использует символ остановки и рассматривает все слова длиной меньше m как слова остановки. Другое определение — оригинальное, использованное Постом (1943) (описанное в исторической справке ниже), в котором единственным останавливающим словом является пустая строка.
Это просто иллюстрация простой двухтеговой системы, в которой используется символ остановки.
2-теговая система Алфавит: {a,b,c,H} Правила производства: а --> ccbaH б --> примерно с --> копияВычисление Начальное слово: баа акка КакбаХ ccbaHcc baHcccc Хккккка (останавливаясь).Эта простая система с двумя тегами адаптирована из De Mol (2008). Он не использует символ остановки, но останавливается на любом слове длиной меньше 2 и вычисляет слегка измененную версию последовательности Коллатца .
В исходной последовательности Коллатца преемником n является либон/2(для четного n ) или 3 n + 1 (для нечетного n). Значение 3 n + 1 явно четно для нечетного n , следовательно, следующий член после 3 n + 1 наверняка будет3 н + 1/2. В последовательности, вычисленной с помощью приведенной ниже системы тегов, мы пропускаем этот промежуточный шаг, следовательно, преемником n является3 н + 1/2для нечетного n .
В этой системе тегов положительное целое число n представлено словом aa...a с n a.
2-теговая система Алфавит: {а,б,в} Правила производства: а --> до нашей эры б --> а с --> аааВычисление Начальное слово: ааа <--> n=3 абв Си-Би-Си дааа аааа <--> 5 ааабк abcbc cbcbc cbcaaa даааааа ааааааа <--> 8 аааааабк аааабcbc aabcbcbc bcbcbcbc bcbcbca bcbcaa бкааа аааа <--> 4 аабк BCBC до н. э. аа <--> 2 До нашей эры а <--> 1 (остановка)Для каждого m > 1 множество систем m -тегов является полным по Тьюрингу ; т. е. для каждого m > 1 это тот случай, когда для любой данной машины Тьюринга T существует система m -тегов, которая эмулирует T . В частности, можно построить систему с двумя тегами для имитации универсальной машины Тьюринга , как это сделали Ван (1963) и Кок и Мински (1964).
И наоборот, можно показать, что машина Тьюринга является универсальной машиной Тьюринга, доказав, что она может эмулировать полный по Тьюрингу класс систем m -тегов. Например, Рогожин (1996) доказал универсальность класса 2-теговых систем с алфавитом { a 1 , ..., a n , H } и соответствующими продукциями { a n a n W 1 , ..., a n a n W n-1 , an n , H }, где W k — непустые слова; Затем он доказал универсальность очень маленькой (4 состояния, 6 символов) машины Тьюринга, показав, что она может моделировать этот класс систем тегов.
Система двух тегов представляет собой эффективный симулятор универсальных машин Тьюринга во времени. То есть, если это детерминированная одноленточная машина Тьюринга, работающая во времени , то существует система с двумя тегами, которая имитирует ее во времени. [3]
Эта версия проблемы остановки является одной из самых простых и легко описываемых неразрешимых задач решения :
Учитывая произвольное положительное целое число n и список из n +1 произвольных слов P 1 , P 2 ,..., P n , Q в алфавите {1,2,..., n }, выполняется повторное применение тега операция t : ijX → XP я в конечном итоге преобразую Q в слово длиной меньше 2? То есть завершается ли последовательность Q , t1 ( Q ) , t2 ( Q ), t3 ( Q ) ,... ?
Приведенное выше определение отличается от определения Поста (1943), чьи системы тегов не используют символ остановки, а останавливаются только на пустом слове, при этом операция тега t определяется следующим образом:
Вышеприведенное замечание относительно полноты по Тьюрингу множества m -систем тегов для любого m > 1 применимо также к этим системам тегов, первоначально определенным Постом.
Согласно сноске в Post (1943), Б. П. Гилл предложил название для более раннего варианта задачи, в котором первые m символов остаются нетронутыми, а вместо этого галочка, указывающая текущую позицию, перемещается вправо на m символов на каждом шаге. . Название проблемы определения того, касается ли галочка когда-либо конца последовательности, затем было названо «проблемой метки», имея в виду детскую игру в метки .
Циклическая система тегов представляет собой модификацию исходной системы тегов. Алфавит состоит всего из двух символов, 0 и 1 , а производственные правила включают список производств, рассматриваемых последовательно, с циклическим возвратом к началу списка после рассмотрения «последнего» производства в списке. Для каждого произведения проверяется самый левый символ слова — если символ равен 1 , текущее произведение добавляется к правому концу слова; если символ равен 0 , к слову не добавляются никакие символы; в любом случае крайний левый символ удаляется. Система останавливается, если слово становится пустым. [4]
Циклическая система тегов Произведения: (010, 000, 1111)Вычисление Начальное слово: 11001 Производственное слово ---------- -------------- 010 11001 000 1001010 1111 001010000 010 01010000 000 1010000 1111 010000000 010 10000000 . . . .
Системы циклических тегов были созданы Мэтью Куком и использовались Куком при демонстрации того, что клеточный автомат по Правилу 110 универсален. [5] Ключевой частью демонстрации было то, что циклические системы тегов могут эмулировать полный по Тьюрингу класс систем тегов.
Система m -тегов с алфавитом { a 1 , ..., a n } и соответствующими постановками { P 1 , ..., P n } эмулируется циклической системой тегов с m*n постановками ( Q 1 , .. ., Q n , -, -, ..., -), где все произведения, кроме первых n , представляют собой пустую строку (обозначаемую ' - '). Q k представляют собой кодировки соответствующего P k , полученные путем замены каждого символа алфавита системы тегов двоичной строкой длиной n следующим образом (они также должны применяться к начальному слову вычисления системы тегов):
а 1 = 100...00 а 2 = 010...00...а н = 000...01
То есть k кодируется как двоичная строка с 1 в k - й позиции слева и 0 в остальных местах. Последовательные строки вычисления системы тегов будут затем кодироваться как каждая ( m*n ) -я строка ее эмуляции циклической системой тегов.
Это очень небольшой пример, иллюстрирующий технику эмуляции.
2-теговая система Правила производства: (a --> bb, b --> abH, H --> H) Кодировка алфавита: a = 100, b = 010, H = 001. Производственные кодировки: (bb = 010 010, abH = 100 010 001, H = 001)Циклическая система тегов Произведения: (010 010, 100 010 001, 001, -, -, -)Вычисление системы тегов Начальное слово: ба абХ Хбб (остановиться)Циклическое вычисление системы тегов Начальное слово: 010 100 (=ba) Производственное слово ---------- ------------------------------- * 010 010 010 100 (=ба) 100 010 001 10 100 001 0 100 100 010 001 - 100 100 010 001 - 00 100 010 001 - 0 100 010 001 * 010 010 100 010 001 (=abH) 100 010 001 00 010 001 010 010 001 0 010 001 010 010 - 010 001 010 010 - 10 001 010 010 - 0 001 010 010 * 010 010 эмулируемая остановка --> 001 010 010 (=Hbb) 100 010 001 01 010 010 001 1 010 010 - 010 010 001 ... ...
Каждая шестая строка (отмеченная ' * '), создаваемая системой циклических тегов, представляет собой кодировку соответствующей строки вычислений системы тегов до тех пор, пока не будет достигнута эмулируемая остановка.
