Унарные языки распознаются двусторонними детерминированными счетными автоматами

2dca (двусторонние детерминированные автоматы с одним счетчиком) (Petersen, 1994) могут распознавать следующий унарный язык:

Есть ли другой нетривиальный унарный язык, распознаваемый 2dca?

Заметьте, что до сих пор неизвестно, могут ли 2dca распознать ?$\mathtt{SQUARE} = \lbrace 0^{n^2} \mid n \geq 0 \rbrace$

ОПРЕДЕЛЕНИЕ: 2dca - это двусторонний детерминированный конечный автомат со счетчиком. 2dca может проверить, является ли значение счетчика нулевым или нет, и увеличивать или уменьшать значение счетчика на 1 на каждом шаге.

Это всего лишь идея, которая пришла мне в голову при чтении Марвина Л. Минского «Рекурсивная неразрешимость проблемы метки Поста и других тем в теории машин Тьюринга»; в частности, знаменитая теорема Ia:

Теорема Ia: Мы можем представить любую частично рекурсивную функцию программой, работающей с двумя целыми числами S 1 и S 2, используя инструкции I j в следующих формах: (i) ДОБАВИТЬ 1 в S j и перейти к I j 1 ( ii) ПОДРЯД 1 из S j , если S j ≠ 0 и перейти к I j 1 , иначе перейти к I j 2 То есть мы можем построить такую ​​программу, которая начинается с S $f(n)$$S_1$$S_2$$I_j$
$S_j$$I_{j_1}$
$S_j$$S_j \neq 0$$I_{j_1}$$I_{j_2}$
и S 2 = 0 и в конечном итоге останавливается с S 1 = 2 f ( n ) и S 2 = $S_1 = 2^n$$S_2 = 0$$S_1 = 2^{f(n)}$$S_2 = 0$

Если у вас есть двусторонний DFA с одним счетчиком на (полу) бесконечной ленте, где ввод задается в унарном виде: тогда DFA может:$\$1^{2^n}000...$

1. прочитать унарный ввод (и сохранить его в счетчике);
2. работать на части ленты и использовать расстояние от 1 с в качестве второго счетчика.$0^\infty$$1$

таким образом, он может моделировать полный счетчик Тьюринга.

Теперь, если у вас есть рекурсивная функция которая выполняется за время T ( n ) на стандартной машине Тьюринга, двусторонний DFA с одним счетчиком, который запускается на конечной ленте $ 1 m$f(n)$$T(n)$ $\$1^m\$ \;$(где и T ′ ( n ) ≫ T ( n ) ) могут:$m = 2^n3^{T'(n)}$$T'(n) \gg T(n)$

1. прочитать унарный ввод (и сохранить его в счетчике);
2. возврат к крайнему левому символу;
3. делим счетчик на 3 до тех пор, пока счетчик не будет содержать таким образом: идите вправо, зацикливаясь на состояния q z 0 , q z 1 , q z 2 и вычитая 1; если счетчик достигает 0 в состоянии q z 0, перейдите к крайнему левому символу, добавив +1 и продолжив цикл деления, в противном случае добавьте 1 (если в состоянии q z 1 ) или 2 (если в состоянии q z 2 ) и перейдите к крайнему левому символу, добавив + 3 (т.е. восстановить предыдущее значение счетчика, не делимого на 3) и перейти к шагу 4 .;$2^n$$q_{z_0}, q_{z_1}, q_{z_2}$$q_{z_0}$$q_{z_1}$$q_{z_2}$
4. в этот момент счетчик содержит ;$2^n$
5. вычислите используя пространство T ′ ( n ), доступное справа в качестве второго счетчика (значение второго счетчика - это расстояние от крайнего левого символа $ ).$2^{f(n)}$$T'(n)$$\$$

Таким образом, с помощью специальной входной кодировки, описанной выше, которая дает достаточно места на конечной ленте, двусторонний DFA с одним счетчиком и унарным алфавитом может вычислять каждую рекурсивную функцию.

Если подход правильный, было бы интересно подумать о том, как выбрать или когда достаточно выбрать большое нечетное k ≫ 2 и кодировать входные данные как 1 m , m = 2 н к $T'(n) \gg T(n)$$k \gg 2$$1^m$$m = 2^n k^n$

Под нетривиальным я предполагаю, что вы имеете в виду язык L, который не может быть принят 1dca. Вот вроде бы такой язык:

ЦЕНТР = {ш | w больше {0,1} * и w = x1y для некоторого x, y такого, что | x | = | y |}

Этот язык не может быть принят 1dca, но МОЖЕТ быть принят 1nca. Это может быть принято 2dca. Детали оставлены в качестве упражнения.