Lenguajes unarios reconocidos por los autómatas deterministas bidireccionales

2dca (autómata determinista bidireccional de un contador) (Petersen, 1994) puede reconocer el siguiente lenguaje unario:

¿Hay algún otro lenguaje unario no trivial reconocido por 2dca?

Observe que todavía se desconoce si 2dca puede reconocer ?$\mathtt{SQUARE} = \lbrace 0^{n^2} \mid n \geq 0 \rbrace$

DEFINICIÓN: Un 2dca es un autómata finito determinista de dos vías con un contador. Un 2dca puede probar si el valor del contador es cero o no, e incrementar o disminuir el valor del contador en 1 en cada paso.

Esta es solo una idea que se me ocurrió mientras leía a Marvin L. Minsky, "La indisolución recursiva del problema de la etiqueta de Post y otros temas en la teoría de las máquinas de Turing"; en particular el famoso teorema Ia:

Teorema Ia: podemos representar cualquier función recursiva parcial mediante un programa que opera en dos enterosS $f(n)$$S_1$ y utilizando las instrucciones I j de las formas: (i) AGREGAR 1 a S j , y pasar a I j 1 (ii ) SUSTRATO 1 de S j , si S j ≠ 0 y va a I j 1 , de lo contrario vaya a I j 2 Es decir, podemos construir un programa que comience con S 1 = 2 $S_2$$I_j$
$S_j$$I_{j_1}$
$S_j$$S_j \neq 0$$I_{j_1}$$I_{j_2}$
$S_1 = 2^n$y y finalmente se detiene con S 1 = 2 f ( n ) y S 2 = $S_2 = 0$$S_1 = 2^{f(n)}$$S_2 = 0$

Si tiene un DFA bidireccional con un contador sobre una cinta (semi) infinita donde la entrada se da en unario: entonces el DFA puede:$\$1^{2^n}000...$

1. lea la entrada unaria (y guárdela en el contador);
2. trabaje en la parte de la cinta y use la distancia desde 1 s como el segundo contador.$0^\infty$$1$

para que pueda simular una máquina Turing completa de dos contadores.

Ahora, si tiene una función recursiva que se ejecuta en el tiempo T ( n ) en una máquina Turing estándar, un DFA bidireccional con un contador que comienza en la cinta finita $ 1 m$f(n)$$T(n)$ $\$1^m\$ \;$(donde y T ′ ( n ) ≫ T ( n ) ) pueden:$m = 2^n3^{T'(n)}$$T'(n) \gg T(n)$

1. lea la entrada unaria (y guárdela en el contador);
2. volver al símbolo más a la izquierda;
3. divida el contador entre 3 hasta que el contador contenga de esta manera: vaya a la derecha en bucle desde los estados q z 0 , q z 1 , q z 2 y reste 1; si el contador alcanza 0 en el estado q z 0, vaya al símbolo más a la izquierda agregando +1 y continúe el ciclo de división; de lo contrario, agregue 1 (si está en el estado q z 1 ) o 2 (si está en el estado q z 2 ) y vaya al símbolo a la izquierda agregando + 3 (es decir, recuperar el valor anterior del contador no divisible por 3) y continuar con el paso 4 .;$2^n$$q_{z_0}, q_{z_1}, q_{z_2}$$q_{z_0}$$q_{z_1}$$q_{z_2}$
4. en este punto el contador contiene ;$2^n$
5. calcule usando el espacio T ' ( n ) disponible a la derecha como el segundo contador (el valor del segundo contador es la distancia desde el símbolo más a la izquierda $ ).$2^{f(n)}$$T'(n)$$\$$

Entonces, con la codificación de entrada especial descrita anteriormente que le da suficiente espacio en la cinta finita, un DFA bidireccional con un contador y un alfabeto unario puede calcular cada función recursiva.

Si el enfoque es correcto, sería interesante razonar sobre cómo elegir o cuándo es suficiente elegir un gran impar k ≫ 2 y codificar la entrada como 1 m , m = 2 n k $T'(n) \gg T(n)$$k \gg 2$$1^m$$m = 2^n k^n$

Por no trivial, supongo que te refieres a un lenguaje L que no puede ser aceptado por 1dca. Aquí parece ser ese lenguaje:

CENTRO = {w | w está por encima de {0,1} * y w = x1y para alguna x, y tal que | x | = | y |}

1dca no puede aceptar este idioma, pero 1nca PUEDE aceptarlo. Puede ser aceptado por un 2dca. Los detalles se dejan como ejercicio.