Secuencia Morse-Thue

La secuencia de Morse-Thue es una secuencia infinita de ceros y unos ( bits ), propuesta por primera vez en 1906 por el matemático noruego Axel Thue como ejemplo de una cadena de caracteres recursivamente computable aperiódica.[ especificar ] . Hay dos variantes de la secuencia, obtenidas una de la otra por inversión de bits:

10010110011010010110100110010110 ... ( secuencia OEIS A010059 ) - opcional 01101001100101101001011001101001… (secuencia A010060 en OEIS ) - principal

La secuencia Morse-Thue es el ejemplo más simple de un fractal y se utiliza en algoritmos de compresión de imágenes fractales .

Definiciones

Una secuencia se puede definir de muchas maneras diferentes equivalentes:

Realización de la transformación ; , tomando para la primera iteración : $0\flecha derecha 01$ $1\flecha derecha 10$ $una$

una diez 1 0 0 1 1 0 0 1 0 1 1 0

Empezamos desde 1. En cada paso, sumamos el inverso de este número al número. La inversión se obtiene reemplazando todos los ceros por unos y los unos por ceros. Por ejemplo, el inverso del número 1001 será el número 0110. (De otra manera, la inversión del número se puede describir de la siguiente manera: este es un número que complementa lo ya escrito a un número que consta solo de unos; por ejemplo, 1001+0110=1111 en el sistema numérico binario)

Paso 1: 1 Paso 2: 10 Paso 3: 1001 Paso 4: 10010110 Paso 5: 1001011001101001 ...

Escribamos los números 0,1,2,3... seguidos en el sistema binario, y contemos el número de dígitos 1 en cada número. (Obtenemos la secuencia A000120 en OEIS ). Luego tomamos el resto de este número cuando lo dividimos por 2.

en notación decimal	en binario	número de unidades	número de unidades módulo 2
0	0	0	0
una	01	una	una
2	diez	una	una
3	once	2	0
cuatro	100	una	una
5	101	2	0
6	110	2	0
7	111	3	una

Historia

La secuencia fue descubierta en 1851 por Prouhet ( fr. E. Prouhet ), quien encontró su aplicación en la teoría de números, pero no describió las propiedades excepcionales de la secuencia. Y recién en 1906, Axel Thue , mientras estudiaba combinatoria, la redescubrió.

La publicación del trabajo de Thue en Alemania pasó sin dejar rastro, y Marson Morse redescubrió la secuencia en 1921, aplicándola en geometría diferencial.

La secuencia se ha descubierto de forma independiente muchas veces: por ejemplo, el gran maestro Max Euwe descubrió su aplicación en el ajedrez, mostrando cómo jugar sin cesar sin romper las reglas de un empate.

Propiedades

Simetrías

Como cualquier fractal , la secuencia de Morse-Thue tiene varias simetrías. Así que la secuencia sigue siendo la misma:

Al eliminar todos los elementos en lugares pares:

10 01 01 10 01 10 10 01 01 10 10 01 10 01 01 10... 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1...

Al sustituir dos partes de las que se puede hacer un todo, por otros dos caracteres. Esto significa que la secuencia no se puede archivar usando el algoritmo de Huffman , ya que la secuencia que es el "archivo" coincidirá con la propia secuencia Morse-Thue:

1001 0110 0110 1001 0110 1001 1001 0110... 1 0 0 1 0 1 1 0...

Otras propiedades

La secuencia nunca contiene tres partes idénticas consecutivas (es imposible encontrar " AAA" , donde " A" - secuencias de ceros y unos);
La transformada discreta de Fourier de la secuencia tiene los mismos máximos en las frecuencias ⅓ y ⅔;
Un número cuya representación binaria es la secuencia de Morse-Thue se denomina número de Prue-Thue-Morse:

\tau =\sum_{{i=0}}^{{\infty}}{\frac {t_{i}}{2^{{i+1}}}}=0.412454033640\ldots

(secuencia A014571 en OEIS ),

donde están los elementos de la secuencia Morse-Thue. Este número es trascendental (probado por K. Mahler en 1929 ). $t_{yo}$

Variaciones y generalizaciones

Generalización a alfabeto arbitrario

Dado un alfabeto arbitrario de n caracteres , uno puede componer exactamente n permutaciones cíclicas diferentes de este alfabeto. Luego, reemplazando cada "letra" del alfabeto con la permutación correspondiente, se puede obtener una secuencia Morse-Thue. Entonces, por ejemplo, se pueden hacer tres permutaciones cíclicas a partir de tres caracteres "1", "2", "3": "123", "231", "312":

1\flecha derecha 123

2\flecha derecha 231

3\flecha derecha 312

una 1 2 3 1 2 3 2 3 1 3 1 2 1 2 3 2 3 1 3 1 2 2 3 1 3 1 2 1 2 3 3 1 2 1 2 3 2 3 1...

Generalización multidimensional

La secuencia multidimensional de Morse-Thue se define de manera similar. Por ejemplo, una sucesión bidimensional (matriz) es el límite de una sucesión, cada miembro siguiente de la cual se obtiene del anterior mediante la transformación

1\rightarrow {\begin{matriz}1&0\\0&1\end{matriz}}

;

0\rightarrow {\begin{matriz}0&1\\1&0\end{matriz}}

10010110\cdots

01101001\cdots

01101001\cdots

10010110\cdots

{\ estilo de visualización \ vdots \ quad \ vdots \ quad \ vdots \ quad \ ddots}

Además, la secuencia bidimensional de Morse-Thue se puede representar como un conjunto de secuencias unidimensionales.

Enlaces

Weisstein, Eric W. Morse -Secuencia de Thue en Wolfram MathWorld .