En referencia a las cadenas de caracteres definidas aquí (construido en varias ocasiones se anexa a la última "la mitad" de la cadena actual), tenga en cuenta la particular infinita cadena de $s$ generado por partida con $\text{abc}$:
$$\begin{align} \quad &\text{abc}\\ &\text{abcbc}\\ &\text{abcbccbc}\\ &\text{abcbccbcccbc}\\ &\cdots\\ &\text{______________________________}\\ s = \ &\text{abcbccbcccbcbcccbccbcbcccbccccb...} \end{align} $$
Más formalmente, el general de la regla de reescritura es $$a_0 a_1 \cdots a_{n-1} \ \ \ \ \ a_0 a_1 \cdots a_{n-1} a_{\left\lfloor\frac{n}{2}\right\rfloor } a_{\left\lfloor\frac{n}{2}\right\rfloor+1} \cdots a_{n-1}. $$ Claramente,
- $\text{a}$ se produce sólo en la posición inicial,
- $\text{b}^k$ se produce infinitamente a menudo para $k=1$, pero nunca se produce por $k\ge2$,
y uno puede conjeturar que
- $\text{c}^k$ se produce para cada $k\ge 1$ (y, por tanto, infinitamente frecuencia para cada una de las $k\ge 1$).
Cómo probar o refutar la conjetura?
Algunos posiblemente-hechos relevantes:
Los cálculos muestran que el índice de la primera ocurrencia de $\text{c}^k$ es de la siguiente manera, para algunos pequeños $k$: $$\begin{align} &\text{substring} \quad & \text{index}\\ &\text{c} &\text{2}\\ &\text{cc} &\text{4}\\ &\text{ccc} &\text{7}\\ &\text{cccc} &\text{26}\\ &\text{ccccc} &\text{27308}\\ &\text{cccccc} &\approx 10^{519}\\ &\text{ccccccc} &? \ (\gt 10^{40677})\\ \end{align} $$ (La exacta índice de la primera ocurrencia de $\text{c}^6$ $520$- dígitos de número y $\text{c}^7$ no se produce en el primer $10^{40677}$ términos de $s$.)
Deje $L_n$ ser la longitud de la $n$th intermedio de la cadena en el proceso de generación de ilustrados anteriormente. Entonces $$L_{n+1} = L_n + \left\lfloor\frac{L_n + 1}{2}\right\rfloor,\ \ L_0 = 3.$$ Por lo tanto, $L_n$ crece exponencialmente: $$L_n \gtrsim 3(\frac{3}{2})^n.$$
Deje $s_n$ $n$th intermedio de la cadena, y deje $t_n$ $n$th anexa cadena (lo $s_n = s_{n-1} t_n$). Ahora, todos los intermedios de la cadena termina con $\text{bc}$, lo $\text{c}^k$ primero sólo se producen cuando algunos $t_n$ comienza con $\text{c}^{k-1}$, en cuyo caso $s_n= s_{n-1} t_n$ contendrá la primera aparición de $\text{c}^k$ inicio índice $L_{n-1}-1$.
Después de $\text{c}^k$ ocurre por primera vez, el número de instancias de $\text{c}^k$ crece aproximadamente de forma exponencial en el número de iteraciones, como lo hace la longitud, y la relación de $$p_k = \frac{\text{número de casos de c}^k\text{ en }n\text{th iteración}}{L_n} \approx \frac{1}{\text{índice de la primera ocurrencia de c}^k} $$ es aproximadamente una constante independiente de $n$. Desde $\text{c}^{k+1}$ primera se produce cuando uno de estos casos de $\text{c}^k$ pasa a comenzar la "última mitad" de un intermedio de la cadena, esto puede ser comparado a una secuencia de ensayos de Bernoulli, cada uno con probabilidad de éxito $p_k$. Para dicho proceso, se espera que el número de ensayos para obtener el primer éxito es $1/p_k$, por lo que el índice de la primera ocurrencia de $\text{c}^{k+1}$ en comparación con $$\frac{2}{3} L_{n_k + 1/p_k} \approx 2(\frac{3}{2})^{n_k + i_k} $$ donde $n_k$ es el número de iteraciones para obtener la primera aparición de $\text{c}^k$, e $i_k$ es el índice correspondiente. E. g., la primera aparición del índice de $\text{c}^6$ en comparación con $2(\frac{3}{2})^{n_5 + i_5} = 2(\frac{3}{2})^{22 + 27308} \approx 10^{4813}$ (cuando en realidad es de aproximadamente $10^{519}$). Del mismo modo, la primera ocurrencia índice de $\text{c}^7$ (si existe) sería en comparación con $2(\frac{3}{2})^{n_6 + i_6} \approx 10^{10^{518}}$. Estas comparaciones son bastante pobres, pero puede ayudar a entender cómo la primera ocurrencia de índices puede ser tan enorme.
