Система тегов

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

Поскольку все указанные операции выполняются за один переход, тег-машина имеет строго только одно состояние.

Система тегов представляет собой триплет ( m , A , P ), где

• m — положительное целое число, называемое числом удаления .
• A — это конечный алфавит символов, один из которых может быть специальным символом остановки . Все конечные (возможно, пустые) строки в A называются словами .
• P — это набор правил продукции , назначающих слово P(x) (называемое продукцией ) каждому символу x в A. Продукция (скажем, P( H ) ), назначенная останавливающему символу, как показано ниже, не играет никакой роли в вычислениях, но для удобства принимается как P( H ) = 'H' .

Остановочное слово — это слово, которое либо начинается с символа остановки, либо длина которого меньше m .

Преобразование t (называемое операцией тега ) определяется на множестве не останавливающихся слов, так что если x обозначает самый левый символ слова S , то t ( S ) является результатом удаления самых левых m символов S и добавления слова P(x) справа. Таким образом, система преобразует m-символьную голову в хвост переменной длины, но сгенерированный хвост зависит исключительно от первого символа головы.

Вычисление с помощью системы тегов представляет собой конечную последовательность слов, полученную путем итерации преобразования t , начиная с изначально заданного слова и останавливаясь, когда производится останавливающее слово. (Согласно этому определению, вычисление не считается существующим, если останавливающее слово не производится за конечное число итераций. Альтернативные определения допускают вычисления без остановки, например, с использованием специального подмножества алфавита для идентификации слов, которые кодируют вывод.)

Термин m-tag system часто используется для подчеркивания числа удалений. Определения несколько различаются в литературе (ср. Ссылки), одно из представленных здесь принадлежит Рогожину. ^[2]

Использование символа остановки в приведенном выше определении позволяет кодировать вывод вычисления только в конечном слове, тогда как в противном случае вывод был бы кодирован во всей последовательности слов, полученных путем итерации операции тега.

Распространенное альтернативное определение не использует символ остановки и рассматривает все слова длиной меньше m как останавливающие слова. Другое определение — это оригинальное, использованное Постом (1943) (описанное в исторической заметке ниже), в котором единственным останавливающим словом является пустая строка.

Это всего лишь иллюстрация простой двухтеговой системы, использующей символ остановки.

2-теговая система Алфавит: {а,б,в,Н} Правила производства: а --> ccbaH б --> около того с --> ссВычисление Начальное слово: baa акка каккбаХ ccbaHcc baHcccc Хккккка (стоп).

Эта простая система из 2 тегов адаптирована из 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-теговая система Алфавит: {а,б,в} Правила производства: а --> до н.э. б --> а с --> аааВычисление Начальное слово: aaa <--> n=3 азбука  cbc кааа ааааа <--> 5 ааабв abcbc cbcbc cbcaaa каааааа ааааааа <--> 8 ааааабв аааабвц аабвцбцбц бцбцбцбц bcbcbca bcbcaa бсааа аааа <--> 4 аабв bcbc бса аа <--> 2 до нашей эры а <--> 1 (остановка)

Для каждого m > 1 множество m -теговых систем является полным по Тьюрингу ; т. е. для каждого m > 1 для любой заданной машины Тьюринга T существует m -теговая система, которая эмулирует T. В частности, можно построить 2-теговую систему для эмуляции универсальной машины Тьюринга , как это сделали Ван (1963) и Коук и Мински (1964).

Наоборот, можно показать, что машина Тьюринга является универсальной машиной Тьюринга, доказав, что она может эмулировать полный по Тьюрингу класс систем m -тегов . Например, Рогожин (1996) доказал универсальность класса систем 2-тегов с алфавитом { a ₁ , ..., an _, H } и соответствующих производств { an _a n W ₁ , ..., an _a n W _{n-1 ,} an a _n , _H } , где W _k — непустые слова ; затем он доказал универсальность очень маленькой (4-состояния, 6-символов) машины Тьюринга, показав, что она может имитировать этот класс систем тегов _.

Система 2-тегов является эффективным симулятором универсальных машин Тьюринга во времени. То есть, если есть детерминированная одноленточная машина Тьюринга, которая работает во времени , то существует система 2-тегов, которая симулирует ее во времени. ^[3]${\displaystyle O(t^{4}\ln ^{2}t)}$${\displaystyle М}$${\displaystyle т}$${\displaystyle O(t^{4}\ln ^{2}t)}$

Эта версия проблемы остановки относится к самым простым и легко описываемым неразрешимым проблемам принятия решений :

Если задано произвольное положительное целое число n и список из n +1 произвольных слов P ₁ , P ₂ ,..., P _n , Q в алфавите {1,2,..., n }, преобразует ли повторное применение операции тега t ​​: ijX → XP _i в конечном итоге Q в слово длиной меньше 2? То есть, завершается ли последовательность Q , t ¹ ( Q ), t ² ( Q ), t ³ ( Q ), ...?

Приведенное выше определение отличается от определения Поста (1943), чьи системы тегов не используют символ остановки, а останавливаются только на пустом слове, при этом операция тега t ​​определяется следующим образом:

• Если x обозначает самый левый символ непустого слова S , то t ( S ) — это операция, состоящая из первого добавления слова P(x) к правому концу S , а затем удаления самых левых m символов результата — удаления всех, если их меньше m символов.

Вышеприведенное замечание относительно полноты по Тьюрингу множества систем m -тегов для любого m > 1 применимо также к этим системам тегов, как они первоначально определены Постом.

Согласно сноске в Post (1943), BP Gill предложил название для более раннего варианта задачи, в котором первые 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 ₁ , ..., a _n } и соответствующими постановками { P ₁ , ..., P _n } эмулируется циклической системой тегов с m*n постановками ( Q ₁ , ..., 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, -, -, -)Расчет системы тегов Начальное слово: ba абХ Hbb (остановка)Циклическое вычисление системы тегов Начальное слово: 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 ... ...

Каждая шестая строка (отмеченная « * »), создаваемая циклической системой тегов, представляет собой кодировку соответствующей строки вычисления системы тегов, пока не будет достигнута эмулируемая остановка.

• Автомат очереди
• Игра жизни Конвея

• Кок, Джон ; Минский, Марвин (1964). «Универсальность систем тегов с P=2». Журнал Ассоциации вычислительной техники . 11 : 15–20. doi : 10.1145/321203.321206. hdl : 1721.1/6107 . S2CID  2799125.
• Кук, Мэтью (2004). «Универсальность элементарных клеточных автоматов». Complex Systems . 15 : 1–40. Архивировано (PDF) из оригинала 28 мая 2016 г.
• De Mol, Liesbeth (январь 2008 г.). «Системы тегов и функции типа Коллатца». Теоретическая информатика . 390 (1): 92–101. doi :10.1016/j.tcs.2007.10.020. hdl : 1854/LU-436211 .
• Минский, Марвин Л. (ноябрь 1961 г.). «Рекурсивная неразрешимость проблемы Поста «Тэга» и других тем в теории машин Тьюринга». Annals of Mathematics . 2. 74 (3): 437–455. doi :10.2307/1970290. JSTOR  1970290.
• Минский, Марвин Л. (1967). Вычисления: Конечные и бесконечные машины. Энглвуд Клиффс, Нью-Джерси: Prentice–Hall . С. 267–273. ISBN 978-0131655638. LCCN  67-12342.
• Пост, Эмиль (1943). «Формальные сокращения комбинаторной проблемы принятия решений». American Journal of Mathematics . 65 (2): 197–215. doi :10.2307/2371809. JSTOR  2371809.(Системы тегов представлены на стр. 203 и далее.)
• Рогожин, Юрий (20 ноября 1996 г.). «Малые универсальные машины Тьюринга». Теоретическая информатика . 168 (2): 215–240. doi :10.1016/S0304-3975(96)00077-1.
• Ван, Хао (1963). «Системы тегов и системы лагов». Математические Аннален . 152 : 65–74. дои : 10.1007/BF01343730. S2CID  120383146.

• https://mathworld.wolfram.com/TagSystem.html
• https://mathworld.wolfram.com/CyclicTagSystem.html
• https://www.wolframscience.com/nks/p95/ (циклические системы тегов)
• https://www.wolframscience.com/nks/p669/ (эмуляция систем тегов)