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

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

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

Определения

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

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

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

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

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

Термин «система m-тегов» часто используется, чтобы подчеркнуть номер удаления. Определения несколько различаются в литературе (см. Библиотеку), здесь представлено определение Рогожина.

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

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

Пример: простая иллюстрация с двумя тегами

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

2-tag system 
    Alphabet: {a,b,c,H} 
    Production rules:
         a  -->  ccbaH
         b  -->  cca
         c  -->  cc

Computation
    Initial word: baa
                    acca
                      caccbaH
                        ccbaHcc
                          baHcccc
                            Hcccccca (halt).

Пример: вычисление последовательностей Коллатца

Эта простая система с двумя тегами адаптирована из De Mol (2008) . Он не использует символ остановки, но останавливается на любом слове длиной меньше 2 и вычисляет слегка измененную версию последовательности Коллатца .

В исходной последовательности Коллатца преемником n является либо n / 2 (для четного n ) или 3 n + 1 (для нечетного n). Значение 3 n + 1 явно четно для нечетного n , следовательно, следующий член после 3 n + 1 наверняка будет 3 н + 1/2 ​ . В последовательности, вычисленной с помощью приведенной ниже системы тегов, мы пропускаем этот промежуточный шаг, следовательно, преемником n является 3 n + 1/2 n нечетного . для

В этой системе тегов положительное целое число n представлено словом aa...a с n a.

2-tag system 
    Alphabet: {a,b,c} 
    Production rules:
         a  -->  bc
         b  -->  a
         c  -->  aaa

Computation
    Initial word: aaa <--> n=3
                    abc  
                      cbc
                        caaa
                          aaaaa  <--> 5
                            aaabc
                              abcbc
                                cbcbc
                                  cbcaaa
                                    caaaaaa
                                      aaaaaaaa  <--> 8
                                        aaaaaabc
                                          aaaabcbc
                                            aabcbcbc
                                              bcbcbcbc
                                                bcbcbca
                                                  bcbcaa
                                                    bcaaa
                                                      aaaa  <--> 4
                                                        aabc
                                                          bcbc
                                                            bca
                                                              aa  <--> 2
                                                                bc
                                                                  a  <--> 1
                                                                   (halt)

по Тьюрингу m тегов

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

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

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

Проблема остановки с двумя тегами

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

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

определении системы тегов

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

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

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

Происхождение названия «тег»

Согласно сноске в Post (1943) , Б. П. Гилл предложил название для более раннего варианта задачи, в котором первые m символов остаются нетронутыми, а вместо этого галочка, указывающая текущую позицию, перемещается вправо на m символов каждый шаг. . Название проблемы определения того, касается ли галочка когда-либо конца последовательности, затем было названо «проблемой тега», имея в виду детскую игру в теги .

Циклические системы тегов

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

Пример

Cyclic Tag System
 Productions: (010, 000, 1111)

Computation
 Initial Word: 11001
    Production         Word
    ----------         --------------
       010             11001
       000              1001010
       1111              001010000
       010                01010000
       000                 1010000
       1111                 010000000
       010                   10000000
        .                      .
        .                      .

Системы циклических тегов были созданы Мэтью Куком и использовались Куком при демонстрации того, что клеточный автомат по Правилу 110 универсален. Ключевой частью демонстрации было то, что циклические системы тегов могут эмулировать полный по Тьюрингу класс систем тегов.

систем тегов циклическими

Система m -тегов с алфавитом { a ₁ , ..., a _n } и соответствующими постановками { P ₁ , ..., P _n } эмулируется циклической системой тегов с m*n постановками ( Q ₁ , .. ., Q _n , -, -, ..., -), где все, кроме первых n произведений, представляют собой пустую строку (обозначаемую ' - '). Q представляют _k собой кодировки соответствующего P _k , полученные путем замены каждого символа алфавита системы тегов двоичной строкой длиной n следующим образом (они также должны применяться к начальному слову вычисления системы тегов):

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

То есть k _с кодируется как двоичная строка 1 в К ^й положение слева и 0 в другом месте. Последовательные строки вычисления системы тегов будут закодированы как каждые ( m*n ) ^й строка его эмуляции циклической системой тегов.

Пример

Это очень небольшой пример, иллюстрирующий технику эмуляции.

2-tag system
    Production rules: (a --> bb, b --> abH, H --> H)
    Alphabet encoding: a = 100, b = 010, H = 001 
    Production encodings: (bb = 010 010, abH = 100 010 001, H = 001)

Cyclic tag system 
    Productions: (010 010, 100 010 001, 001, -, -, -)

Tag system computation
    Initial word: ba
                    abH
                      Hbb (halt)

Cyclic tag system computation
    Initial word: 010 100 (=ba)

    Production       Word
    ----------       -------------------------------
  * 010 010          010 100  (=ba)
    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       emulated halt -->  001 010 010  (=Hbb)
    100 010 001                       01 010 010
    001                                1 010 010
    -                                    010 010 001
    ...                                    ...

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

См. также

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

Ссылки

• Кок, Джон ; Мински, Марвин (1964). «Универсальность систем тегов с P=2». Журнал Ассоциации вычислительной техники . 11 :15–20. дои : 10.1145/321203.321206 . hdl : 1721.1/6107 . S2CID   2799125 .
• Кук, Мэтью (2004). «Универсальность в элементарных клеточных автоматах» . Сложные системы . 15 :1–40. Архивировано (PDF) из оригинала 28 мая 2016 года.
• Де Моль, Лисбет (январь 2008 г.). «Системы тегов и функции, подобные Коллатцу». Теоретическая информатика . 390 (1): 92–101. дои : 10.1016/j.tcs.2007.10.020 . hdl : 1854/LU-436211 .
• Мински, Марвин Л. (ноябрь 1961 г.). «Рекурсивная неразрешимость проблемы Поста о «теге» и других тем теории машин Тьюринга». Анналы математики . 2. 74 (3): 437–455. дои : 10.2307/1970290 . JSTOR   1970290 .
• Мински, Марвин Л. (1967). Вычисления: конечные и бесконечные машины . Энглвуд Клиффс, Нью-Джерси: Прентис – Холл . стр. 267–273. ISBN  978-0131655638 . LCCN   67-12342 .
• Пост, Эмиль (1943). «Формальные редукции проблемы комбинаторного решения» . Американский журнал математики . 65 (2): 197–215. дои : 10.2307/2371809 . JSTOR   2371809 . (Системы тегов представлены на стр. 203 и далее .)
• Рогожин, Юрий (20 ноября 1996 г.). «Маленькие универсальные машины Тьюринга». Теоретическая информатика . 168 (2): 215–240. дои : 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/ (эмуляция систем тегов)