Я пытался выяснить, разрешима ли проблема остановки для трехмерных одномерных клеточных автоматов.
Определение Пусть обозначает конфигурацию системы на временном шаге i . Более формально f : A ∗ × N → A ∗ , где A - алфавит.
Определение. Сотовый автомат остановился в конфигурации , если ∀ k ∈ N , то f ( w , i ) = f ( w , i + k ) .
Проблема остановки для данного клеточного автомата заключается в следующем:
Ввод: конечное слово Вопрос: остановится ли автомат в каком-то состоянии s ?
Элементарные клеточные автоматы (с 2 символами) определены здесь . Я сфокусирован на одном и том же виде целуллярных автоматов, за исключением того, что меня интересует случай CA с 3 символами вместо 2 символов.
Отныне я буду обозначать свои правила в виде , что означает, что 3 соседних символа производят еще один под ними.
Проблема остановки решаема для элементарных 2-символьных клеточных автоматов
Я буду использовать для обозначения белой клетки и 1 для обозначения черной.
Если у нас есть правила , 001 → 1 , 100 → 1, мы знаем, что автомат не остановится. Потому что с первым правилом, поскольку наша сетка бесконечна, у нас всегда будет 3 белых клетки, которые будут генерировать черные клетки. Со вторым и третьим правилами слово будет расширяться в стороны, и автомат никогда не остановится.
В остальных случаях мы можем позволить ему развиваться за шагов и посмотреть, остановится ли он. Если он останавливается, тогда хорошо, он останавливается, если нет, он повторяет некоторые комбинации и застревает в цикле, поэтому мы также можем сделать вывод, что он не остановится.
Что я понял для случая с 3 символами
Очевидно, что он не остановится, если у нас есть правила или 000 → 2 . Но побочные правила вида 00 x → y и x 00 → y сложнее анализировать, потому что, если у нас есть правила 002 → 1 и 001 → 0 ?
Вот что я придумал:
давайте рассмотрим все комбинации таких правил:
- и 002 → 0
- и 002 → 1
- и 002 → 2
- и 002 → 0
- и 002 → 1
- и 002 → 2
- и 002 → 0
- и 002 → 1
- и 002 → 2
Я не писал случаев для правил вида , потому что они симметричны.
Итак, в первом случае очевидно, что входное слово не будет расширяться в стороны, потому что эти правила побочных символов производят нули.
В случаях 5, 6, 8, 9 очевидно, что автомат никогда не остановится, потому что входное слово будет расширяться.
Случаи 2,3,4,7 более интересны. Во-первых, давайте отметим, что случай 2 аналогичен случаю 7, а случай 3 аналогичен случаю 4. Итак, давайте просто рассмотрим случаи 2 и 3 для краткости.
Сначала я собираюсь рассмотреть случай 3, потому что это проще.
Вот все комбинации, которые мы должны рассмотреть:
010 011 012
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
........... etc
Объяснение того, что произойдет, если у нас есть первая тройка из таблицы выше
Обобщенный случай 3
Где я застрял
Теперь давайте рассмотрим случай 2.
И вот где я застрял и не знаю, что делать.
Вот таблица:
010 011 012
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2
Ребята, вы можете сказать мне, как это решить? Я не могу обернуться вокруг этого.
Или, если этот клеточный автомат с 3 символами выглядит как нечто, решение проблемы остановки которого оказалось неразрешимым, как я могу уменьшить это значение до 3 клеточных автоматов с 3 символами?
Ответы:
Я нашел эту статью: http://www.dna.caltech.edu/~woods/download/NearyWoodsMCU07.pdf и покажу, как доказать, что проблема остановки неразрешима для клеточных автоматов с 15 символами.
Давайте посмотрим на типичные инструкции машины Тьюринга:
Давайте посмотрим, как мы можем моделировать операции ТМ. Давайте рассмотрим второй первый:
Первый случай немного сложнее, у нас есть:
первый шаг:
второй шаг:
Что касается всех других правил CA, для которых в TM нет правил, мы напишем следующее:
Итак, теперь есть промежуток между 2 и 15 символами (исключая), о котором мы не знаем.
источник