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

Речь идет о КА схожих с элементарными (двухсимвольными одномерными КА), описанными тут. Единственное отличие в том, что у тех двухсимвольный алфавит, а у меня трёхсимвольный.

Пусть конфигурация ленты это такая функция $%f:\Sigma^\star \times \mathbb{N}\to\Sigma^\star$%,которая говорит нам что будет написано на ленте, через какое-то количество шагов: то есть $%f(w,i)$% выводящее какое-то $%w'$% будет означать, что при входном слове $%w$%, через $%i$% шагов будет $%w'$%.

Под остановкой я имею в виду такую конфигурацию $%f(w,i)$%, что $%f(w,i)=f(w,i+k),$% $%\forall k\in \mathbb{N}.$%

Она разрешима для 2х символьных КА.

Чтобы это доказать, рассмотрим правила 000->1, 001->1, 100->1.

При правиле 000->1, наш автомат превращает все граничащие тройки белых клеток в черные клетки. Т.к. лента бесконечна в обе стороны, то при наличии этого правила можно сразу сказать, что автомат не остановится.

При правилах 001->1 и 100->1, он будет разрастаться по бокам, и тоже не остановится, следовательно при наличии таких правил можно тоже сказать, что автомат не остановится.

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

Что я надумал с 3х символьным случаем.

Ясно, что при правилах 000->1 и 000->2 система не остановится (исходя из эквивалентного аргумента для элементарных КА).

Теперь рассмотрим правила вида 00x->y и x00->y. Они симметричны, поэтому я рассмотрю только 00x->y.

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

1) 001->0 и 002->0
2) 001->0 и 002->1
3) 001->0 и 002->2
4) 001->1 и 002->0
5) 001->1 и 002->1
6) 001->1 и 002->2
7) 001->2 и 002->0
8) 001->2 и 002->1
9) 001->2 и 002->2

Очевидно, при первом случае автомат остановится, потому что слово будет сужаться.

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

Оставшиеся случаи 2, 3, 4, 7. Заметим, что случай 2 симметричен случаю 7, а случай 3, случаю 4. Поэтому я рассмотрю только случаи 2 и 3.

Случай 3.

Имеем правила 001->0 и 002->2. Тут Автомату можно дать проделять 3^n шагов и если на каком-то из этих шагов у нас первым или последним символом стала '2', то можем заключить, что автомат не остановится, из-за правила 002->2. Если же символа '2' не появилось и автомат не остановился, то он в периодичном состоянии, следовательно он не остановится. Если же остановился, то ок, остановился.

Случай 2.

Имеем правила 001->0 и 002->1. Тут всё намного сложнее, потому что непонятно когда у нас слово разрастается, а когда нет. Я решил проанализировать правила вида 01x->y, именно они могут вывести '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

Ясно, что, например, при последней тройке 01x всегда выводит '2', следовательно автомат не остановится. При случаях, когда '2' не выводится ни одним правилом вида 01x->y не нужно беспокоиться о разрастании слова (кроме первого шага, потому что изначально '2' может быть во входном слове), и можно проделать 3^n + 1 шагов, и посмотреть вошел ли автомат в периодичность или остановился.

А вот случаи, где есть '2' в выше написанных тройках, я не знаю как анализировать, там получается как-то запутано всё, и зависит от входного слова. Я не могу просто сказать "тут она неразрешима, потому что тут сложно", вот и хотел поинтересоваться, как быть дальше?

С одной стороны, ясно, что если есть, например, правило 012->2, выводящее '2', то потом можно рассмотреть правила вида 02x->y, если они все выводят '2', то на следующем шаге у нас опять появится "012" с края:

....012...
....02....
....12....
...02....
...12....
etc... до бесконечности.

Если же все 02x->y выводят '0', то ясно, что слово не разрастётся. Но всё это как-то слишком запутанно и даже для тройки <0,0,2> из вышеописанной таблицы мне надо рассматривать 3^22 случаев, и то они ни о чем не скажут, потому что всё тут всё еще будет зависеть от входного слова.

UPDATE: тут http://cs.stackexchange.com/questions/52655/is-the-halting-problem-decidable-for-3-symbol-one-dimensional-cellular-automata я написал почему она неразрешима для 15 символов.