Система тегов - Tag system

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

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

Определения

А система тегов является тройкой (м, А, п), куда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Система с двумя тегами Алфавит: {a, b, c} Правила производства: a -> bc b -> ac -> aaa Вычисление Начальное слово: 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 (остановка)

Тьюринговая полнота мсистемы тегов

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

То есть, аk кодируется как двоичная строка с 1 в kth положение слева, и 0в другом месте. Последовательные строки вычисления системы тегов затем будут закодированы как каждые (м * п)th линия его эмуляции системой циклических тегов.

Пример

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

Система с двумя тегами Правила производства: (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 abH Hbb (остановка) Расчет системы циклических тегов Начальное слово: 010 100 (= ba) Производственное слово ---------- ------------------------------- * 010 010 010 100 (= ba) 100 0100 001 10 100 001 0100100 010 001 - 100 100 0100 0001 - 00 100 010 001 - 0100 010 001 * 010 010 100 010 001 (= abH) 100 010 001 00 0100 001 010 0100001 0 010 001 010 010 - 0100001010010 - 100001010010 - 001 010 010 * 010 010 эмулированная остановка -> 001010 010 (= Hbb) 100 010 001 01010 0100001 1010 010 - 010 010 001 ... ...

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

Смотрите также

Примечания

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

Рекомендации

  • Кок, Дж., и Минский, М .: «Универсальность теговых систем с P = 2», J. Assoc. Comput. Мах. 11, 15–20, 1964.
  • Де Мол, Л .: "Системы тегов и функции типа Коллатца", Теоретическая информатика , 390:1, 92–101, январь 2008 г. (Препринт № 314.)
  • Марвин Мински 1961, Рекурсивная неразрешимость проблемы Поста о «теге» и других разделов теории машин Тьюринга », Анналы математики, 2-й сер., Vol. 74, № 3. (ноябрь 1961 г.), стр. 437–455. JSTOR  1970290.
  • Марвин Мински, 1967, Вычисления: конечные и бесконечные машины, Prentice-Hall, Inc., Englewoord Cliffs, N.J., без 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.
  • Ван, Х.: "Системы тегов и системы лагов", Математика. Annalen 152, 65–74, 1963.

внешняя ссылка