Система меток
-
Определение системы меток
- Система меток — это конечная последовательность слов, созданная путем повторения преобразования t.
- Преобразование t состоит в добавлении слова P(x) к концу слова S и удалении первых m символов результата.
-
Примеры систем меток
- Пример системы из 2 меток: aa…a для четных чисел и 3n + 1 для нечетных чисел.
- Пример системы из 3 меток: aa…a для четных чисел, 3n + 1 для нечетных чисел и 5n + 2 для чисел, кратных 5.
-
Тьюринг-полнота систем меток
- Для каждого m > 1 система m-меток является полной по Тьюрингу, что означает возможность эмуляции любой машины Тьюринга.
- Рогожин (1996) показал универсальность класса 2-теговых систем и эффективность эмуляции универсальной машины Тьюринга.
-
Проблема остановки с системой меток
- Проблема остановки с системой меток — это неразрешимая задача определения, остановится ли последовательность слов, сгенерированных системой меток.
-
Историческая справка
- Определение системы меток отличается от определения Post (1943), где используется только остановка на пустом слове.
- Название «тег» было предложено Б. P. Гиллом, а проблема остановки была названа «проблемой пятнашек».
-
Циклические системы меток
- Циклическая система меток — это модификация исходной системы меток с циклическим возвратом к началу списка производств.
- Циклические системы меток могут эмулировать класс систем меток, полный по Тьюрингу.
-
Эмуляция систем меток с помощью циклических систем меток
- Эмуляция систем меток с помощью циклических систем меток возможна путем кодирования слов исходной системы меток в двоичные строки.
- Каждая (m*n)-я строка эмуляции циклической системы меток является кодировкой соответствующей строки вычисления исходной системы меток.