Разрешаема ли проблема остановки для трехмерных одномерных клеточных автоматов?

10

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

Определение Пусть обозначает конфигурацию системы на временном шаге i . Более формально f : A × NA , где A - алфавит.f(w,i)if:A×NAA

Определение. Сотовый автомат остановился в конфигурации , если k N , то f ( w , i ) = f ( w , i + k ) .f(w,i)kNf(w,i)=f(w,i+k)

Проблема остановки для данного клеточного автомата заключается в следующем:

Ввод: конечное слово Вопрос: остановится ли автомат в каком-то состоянии s ?w
s

Элементарные клеточные автоматы (с 2 символами) определены здесь . Я сфокусирован на одном и том же виде целуллярных автоматов, за исключением того, что меня интересует случай CA с 3 символами вместо 2 символов.

Отныне я буду обозначать свои правила в виде , что означает, что 3 соседних символа производят еще один под ними.

Проблема остановки решаема для элементарных 2-символьных клеточных автоматов

Я буду использовать для обозначения белой клетки и 1 для обозначения черной.01

Если у нас есть правила , 001 1 , 100 1, мы знаем, что автомат не остановится. Потому что с первым правилом, поскольку наша сетка бесконечна, у нас всегда будет 3 белых клетки, которые будут генерировать черные клетки. Со вторым и третьим правилами слово будет расширяться в стороны, и автомат никогда не остановится.000100111001

В остальных случаях мы можем позволить ему развиваться за шагов и посмотреть, остановится ли он. Если он останавливается, тогда хорошо, он останавливается, если нет, он повторяет некоторые комбинации и застревает в цикле, поэтому мы также можем сделать вывод, что он не остановится.2n

Что я понял для случая с 3 символами

Очевидно, что он не остановится, если у нас есть правила или 000 2 . Но побочные правила вида 00 x y и x 00 y сложнее анализировать, потому что, если у нас есть правила 002 1 и 001 0 ?0001000200xyx00y00210010

Вот что я придумал:

давайте рассмотрим все комбинации таких правил:

  1. и 002 000100020
  2. и 002 100100021
  3. и 002 200100022
  4. и 002 000110020
  5. и 002 100110021
  6. и 002 200110022
  7. и 002 000120020
  8. и 002 100120021
  9. и 002 200120022

Я не писал случаев для правил вида , потому что они симметричны.x00y

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

В случаях 5, 6, 8, 9 очевидно, что автомат никогда не остановится, потому что входное слово будет расширяться.

Случаи 2,3,4,7 более интересны. Во-первых, давайте отметим, что случай 2 аналогичен случаю 7, а случай 3 аналогичен случаю 4. Итак, давайте просто рассмотрим случаи 2 и 3 для краткости.

Сначала я собираюсь рассмотреть случай 3, потому что это проще.

00100022222

Вот все комбинации, которые мы должны рассмотреть:

010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
........... etc

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

w101000110012020022|w|/2

Обобщенный случай 3

3n2

Где я застрял

Теперь давайте рассмотрим случай 2.

00100021

И вот где я застрял и не знаю, что делать.

122s101xy

Вот таблица:

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

23n2

2

Ребята, вы можете сказать мне, как это решить? Я не могу обернуться вокруг этого.

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

Павел
источник
2
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат . Если что-то выйдет из этого обсуждения, пожалуйста, отредактируйте вопрос, чтобы включить новую информацию или разъяснения. Не добавляйте отметки «РЕДАКТИРОВАТЬ:», убедитесь, что новичок может понять вопрос, не копаясь в истории.
Жиль "ТАК - перестань быть злым"

Ответы:

1

Я нашел эту статью: http://www.dna.caltech.edu/~woods/download/NearyWoodsMCU07.pdf и покажу, как доказать, что проблема остановки неразрешима для клеточных автоматов с 15 символами.

Давайте посмотрим на типичные инструкции машины Тьюринга:

q,xp,y,L

q,xp,y,R

xqxyp

ARQΣ=AQ{q|qrR,r=p,xq,y,L}qp,xq,y,Lq

s=...xabqzyk...qQqz

Давайте посмотрим, как мы можем моделировать операции ТМ. Давайте рассмотрим второй первый:

q,zp,y,R

s=...xabqzyk......xabypyk...

qzαp,αΣ

αqzy,αΣ

Первый случай немного сложнее, у нас есть:

q,zp,y,L

s=...xabqzyk......xapbyyk...abqpabq

первый шаг:

qzαy,αΣ

αqzp,αΣ

второй шаг:

αβpp,α,βΣ

αpββ,α,βΣ

Что касается всех других правил CA, для которых в TM нет правил, мы напишем следующее:

αβγβ,α,β,γΣ

U6,4

введите описание изображения здесь

qp,xq,y,Lu1,u3,u4,u5,u6

Итак, теперь есть промежуток между 2 и 15 символами (исключая), о котором мы не знаем.

Павел
источник