Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Определения [ править ]

Система тегов - это тройка ( m , A , P ), где

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

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

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

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

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

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

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

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

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

2-х теговая система  Алфавит: {a, b, c, H}  Правила производства: а -> ccbaH b -> cca c -> ccВычисление Начальное слово: baa акка caccbaH ccbaHcc baHcccc Hcccccca (остановка).

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

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

Тьюринг-полнота м -tag систем [ править ]

Показывает процесс эмуляции машины Тьюринга с помощью системы тегов [2]

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

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

Пример использования системы тегов для имитации машины Тьюринга на языке Wolfram Language см. В статье «Новый вид науки» или на графике справа.

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

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

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

Историческая справка об определении системы тегов [ править ]

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

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

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

Происхождение названия "тег" [ править ]

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

Циклические системы тегов [ править ]

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

Пример [ править ]

Циклическая система тегов Производств: (010, 000, 1111)Вычисление Начальное слово: 11001 Производственное слово ---------- -------------- 010 11001 000 1001010 1111 001010000 010 01010000 000 1010000 1111 010000000 010 10000000 . . . .

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

Эмуляция систем тегов с помощью циклических систем тегов [ править ]

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

а 1 = 100 ... 00 а 2 = 010 ... 00...а п = 000 ... 01

То есть, к кодируется в виде бинарной строки с 1 в к - й позиции с левой стороны , и 0 «S в другом месте. Затем последующие строки вычисления системы тегов будут закодированы как каждая ( m * n ) -я строка ее эмуляции системой циклических тегов.

Пример [ править ]

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

2-х теговая система Правила постановки: (a -> bb, b -> abH, H -> H) Кодировка по алфавиту: a = 100, b = 010, H = 001  Кодировки продукции: (bb = 010 010, abH = 100 0100 001, H = 001)Система циклических тегов  Производства: (010 010, 100 0100 001, 001, -, -, -)Расчет системы тегов Начальное слово: ba abH Hbb (остановка)Расчет системы циклических тегов Начальное слово: 010 100 (= ba) Производственное слово ---------- ------------------------------- * 010 010 010 100 (= ba) 100 010 001 10 100 001 0100 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 ... ...

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

См. Также [ править ]

  • Автомат очереди

Заметки [ править ]

  1. ^ Новый вид науки [1]
  2. ^ Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media. п. 670. ISBN 1579550088.
  3. ^ a b Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. стр. 95 . ISBN 1-57955-008-8.
  4. ^ Новый вид науки [2]

Ссылки [ править ]

  • Кок, Дж. , Мински , М .: «Универсальность систем меток с P = 2», J. Assoc. Comput. Мах. 11 , 15–20, 1964.
  • Де Мол, Л .: "Системы тегов и функции типа Коллатца", Теоретическая информатика , 390: 1 , 92–101, январь 2008 г. ( Препринт № 314. )
  • Марвин Мински, 1961, Рекурсивная неразрешимость проблемы Поста о «теге» и других разделах теории машин Тьюринга », Анналы математики, 2-я сер., Том 74, № 3. (ноябрь 1961), стр. 437 -455. JSTOR  1970290 .
  • Марвин Мински , 1967, Вычисления: конечные и бесконечные машины , Прентис-Холл, Инк. Энглворд Клиффс, Нью-Джерси, без ISBN, номер в каталоге карточек Библиотеки Конгресса 67-12342.
В главе 14, озаглавленной «Очень простые основы вычислимости», Мински представляет очень удобочитаемый (с примерами) подраздел 14.6 «Проблема« тегов »и моногенных канонических систем» (стр. 267–273) (этот подраздел обозначен как « система тегов "). Мински рассказывает о своем разочаровывающем опыте с общей проблемой: «Пост нашел эту (00, 1101) проблему« неразрешимой », и я тоже, даже с помощью компьютера». Он комментирует, что «эффективный способ решить для любой строки S, будет ли этот процесс когда-либо повторяться при запуске с S» неизвестен, хотя несколько конкретных случаев оказались неразрешимыми. В частности, он упоминает теорему Кока и следствие 1964 года.
  • Пост, Э .: "Формальные сокращения комбинаторной проблемы принятия решений", Американский журнал математики , 65 (2), 197–215 (1943). (Системы тегов представлены на стр. 203 и далее.)
  • Рогожин Ю. М. Универсальные малые машины Тьюринга // ТМФ. Comput. Sci. 168 , 215–240, 1996.
  • Ван, Х .: "Системы тегов и системы запаздывания", Math. Аннален 152 , 65–74, 1963.

Внешние ссылки [ править ]

  • http://mathworld.wolfram.com/TagSystem.html
  • http://mathworld.wolfram.com/CyclicTagSystem.html
  • http://www.wolframscience.com/nksonline/page-95 (системы циклических тегов)
  • http://www.wolframscience.com/nksonline/page-669 (эмуляция систем тегов)