Probar que el conjunto de poderes de 2 sobre el alfabeto ternario no es regular.

Es simple ver que los poderes de 2 sobre el alfabeto {0,1} son regulares porque $10^*$ es una expresión regular para ello.

Pero los poderes de 2 representados en ternario parecen no ser regulares. El bombeo de clases de lema o residuos es difícil de aplicar, ya que parece haber muy poco patrón entre las cadenas. ¿Cómo lo resuelvo?

En general, para qué potencias de $k$ representan en la base $r$ , ¿es regular el conjunto?

Aquí hay una solución alternativa (con explicación detallada) usando el Teorema de Myhill-Nerode. Usaré la base y 2 para la lectura, pero la prueba generaliza para las bases arbitrarias r , k que no son potencias del mismo número entero.$3$$2$$r,k$

(1) Muestre que, dada cualquier cadena ternaria , existe otra cadena y tal que x y es una potencia de 2 .$x$$y$$xy$$2$

Prueba: Dada cualquier (dejando que n sea ​​el número que representa), ∀ k y c ∈ { 0 , ... , 3 k - 1 } , existe y tal que x y representa 3 k n + c . De hecho, esto caracteriza todos los números que x y puede representar. Por lo tanto, encontrar el mínimo y tal que x y sea ​​una potencia de 2 depende de encontrar el número entero más pequeño $x$$n$$\forall k$$c\in \{0,\ldots,3^k-1 \}$$y$$xy$$3^kn + c$$xy$$y$$xy$$2$$k$de modo que tengamos una potencia de en el intervalo [ 3 k n , 3 k ( n + 1 ) - 1 ] . Tomando log base 2 , necesitamos encontrar k tal que tengamos un número entero en el intervalo [ k log 3 + log x , k log 3 + log ( x + 1 ) ] (dejando caer el - $2$$[3^kn,3^k(n+1)-1]$$2$$k$$[k\log 3 + \log x, k\log3 + \log(x+1)]$$-1$aquí es dudoso, pero simplifica los cálculos que no dependen de él). Tenga en cuenta que cambiar solo afecta a la porción k log 3 , por lo que podemos encontrar una k que nos acerque arbitrariamente a algún número entero.$k$$k\log 3$$k$

(2) Dada algo de y el mínimo y correspondiente , demuestre que existe una cadena x 'tal que el mínimo y correspondiente ' debe ser mayor que y . Repetir esto nos da infinitamente muchas clases de cadenas de equivalencia.$x$$y$$y'$$y$

Esquema de prueba: Dado que , dada una x y sus correspondientes y y k siempre podemos encontrar algunos x ′ = 2 m x donde log ( 2 m x + 1 ) - log ( 2 m x ) es lo suficientemente pequeño como para no contener ningún número entero en [ k log 3 + m + log x $\log 2^m x = m + \log x$$x$$y$$k$$x' = 2^m x$$\log(2^m x + 1) - \log (2^m x)$ . Tenga en cuenta que estamos usando implícitamente el hecho de que k log 3 + log x nunca puede ser un número entero.$[k\log 3 + m +\log x, k\log3 + \log(2^mx+1)]$$k\log 3 + \log x$

En general, para qué potencias de representan en la base r , ¿es regular el conjunto?$k$$r$

Su pregunta es un subcampo del Teorema de Cobham (Alan Cobham, Sobre la dependencia básica de conjuntos de números reconocibles por autómatas finitos, Theory of Computing Systems 3 (2): 186--192, 1969, doi: 10.1007 / BF01746527 ):

Deje que sea un conjunto de números enteros no negativos y dejar que m y n son enteros positivos multiplicativa independientes. Entonces S es reconocible por autómatas finitos en tanto m ary y n notación ary si y sólo si es en última instancia periódica$S$$m$$n$$S$$m$$n$

Aquí, por multiplicativamente independiente, uno significa que no existe un valor distinto de cero y q tal que m p = n q . Cobham cita a Büchi para su caso específico de poderes de algunos k en la base r , que es reconocible solo si k y r son dependientes multiplicativamente .$p$$q$$m^p=n^q$$k$$r$$k$$r$

Si está interesado en este resultado, hay una encuesta bastante agradable de Véronique Bruyère, Georges Hansel, Christian Michaux y Roger Villemaire (Lógica y conjuntos de enteros reconocibles por , Boletín de la Sociedad Matemática Belga 1 (2), 1994, PDF ), que también muestra la relación con la aritmética de Presburger.$p$

El lema de bombeo implica que hay una secuencia como para algunos b , c , d , de modo que cada x n es una potencia de k . Entonces log k ( x n ) = d n log k ( r ) + c o n s t $x_n = c+b(r^{dn}-1)/(r^d-1)$$b,c,d$$x_n$$k$ es siempre un número entero, por lo que log k ( r ) es racional.$\log_k(x_n)=dn \log_k(r) + const + o(1)$$\log_k(r)$

Aquí hay una explicación de esa fórmula para . El lema de bombeo da las cadenas u , v , w de modo que cada cadena x n = u v n w es una potencia de k . Interpretación de estas cadenas como números y la escritura d y e para las longitudes de v y w respectivamente, x n = u r d n + e + v r d ( n - 1 $x_n$$u,v,w$$x_n=u v^n w$$k$$d$$e$$v$$w$es una potencia ded. Entonces x n - x n - 1 =(u r d -u+v) r d ( n - 1 ) + e . Escribirb=(u r d -$x_n = u r^{dn+e} + v r^{d(n-1)+e} + v r^{d(n-2)+e} + \dotsb + v r^e + w$$d$$x_n-x_{n-1} = (u r^d - u + v) r^{d(n-1)+e}$ y c = x 0 - b tenemos x n = c + b ( r d n - 1 ) / ( r d - 1 ) .$b=(u r^d - u + v)r^e$$c=x_0-b$$x_n=c+b(r^{dn}-1)/(r^d-1)$

Sea $L$ el conjunto de potencias de 2 codificadas en la base 3. La codificación de $4^n$ en la base 3 termina con 1, mientras que la codificación de $2\cdot 4^n$ en la base 3 termina con 2. Por lo tanto, $L' = L \cap \Sigma^*1$ es la codificación de todos los poderes de 4.

La codificación de un entero $m > 0$ en la base 3 toma $\lceil \log_3 (m+1) \rceil$ dígitos. Como ni $4^n$ ni $4^n+1$ son potencias de 3 para $n>0$ (dado que ninguno es divisible por 3), la codificación de $4^n$ toma $\lfloor \log_3 4^n \rfloor + 1$ dígitos.

Deje $N = \{ \lfloor \log_3 4^n \rfloor : n \geq 0 \}$ (esta es una secuencia Beatty ). Supongamos que $L$ fuera regular. Entonces también lo sería $L'$ . Esto implica que el conjunto de longitudes de palabras en $L'$ es eventualmente periódico, por lo que $N$ es eventualmente periódico. En particular, $N$ tendría densidad racional asintótica. Sin embargo, $N$ tiene densidad asintótica $1/\log_3 4$ , lo cual es irracional.