4.5: Cómo codificar una secuencia de números
- Page ID
- 113511
Supongamos que tenemos una secuencia finita de números, tal vez
\[2, 4, 3, 5, 9\]
y deseamos codificarlos como un solo número. Una manera fácil de hacer esto sería codificar la secuencia en los exponentes de los primeros números primos y luego multiplicarlos juntos:
\[2^2 \cdot 3^4 \cdot 5^3 \cdot 7^5 \cdot 11^9 = 1605016087126798500.\]
Esto sería fácil, pero desgraciadamente no bastará para nuestros propósitos, así que tendremos que ser un poco más furtivos. Afortunadamente, al ser astutos ahora, la vida será más sencilla después, por lo que parece valer la pena el esfuerzo.
Probablemente estés pensando que sería fácil decidir si un número era un código para una secuencia. Obviamente\(72 = 2^3 3^2\) quiere ser el código para la secuencia\(3, 2\), y el número 10 no es un número de código, ya que no\(10 = 2 \cdot 5\) es producto de los primeros primos.
Lo siento.
Tu idea perfectamente fina se mete en problemas si tratamos de codificar secuencias que incluyan el número 0. Por ejemplo, si tuviéramos que codificar la secuencia
\[1, 0, 1\]
obtendríamos\(2^1 \cdot 3^0 \cdot 5^1 = 10\), y así 10 debería ser un número de código. Pero tu idea de codificar las cosas como exponentes realmente fue buena, y podemos guardarla si solo estamos de acuerdo en que siempre que queramos codificar una secuencia finita de números\(a_1, a_2, \ldots, a_k\), usaremos los exponentes\(a_1 + 1, a_2 + 1, \ldots, a_k + 1\), que se encarga de esos molestos 0. Además, cuando descodificamos restaremos automáticamente uno de cada exponente, así que nunca tendrás que pensarlo. (¡Oye, por eso a nosotros, a los autores, nos pagan los grandes dólares!)
La idea aquí es que una secuencia de números\(k\) naturales debe ser codificada por un producto de los primeros\(k\) primos elevados a potencias distintas de cero. Entonces la secuencia vacía, naturalmente, será codificada por un producto de los primeros 0 primos elevados a alguna potencia. Es decir, el código de la secuencia vacía será el número 1. Hagamos esto más formal:
La función\(p\) es la función que mapea los números naturales a los números naturales, donde\(p \left( 0 \right) = 1\) y\(p \left( k \right)\) es el\(k^\text{th}\) primo para\(k \geq 1\). Así\(p \left( 0 \right) = 1\),\(p \left( 1 \right) = 2\),\(p \left( 2 \right) = 3\), y así sucesivamente. A menudo escribiremos\(p_i\) en lugar de\(p \left( i \right)\).
Dejar\(\mathbb{N}^{< \mathbb{N}}\) denotar el conjunto de secuencias finitas de números naturales.
Definimos la función de codificación\(\langle \cdot \rangle : \mathbb{N}^{M \mathbb{N}} \rightarrow \mathbb{N}\) por
\[\langle \left( a_1, a_2, \ldots, a_k \right) \rangle = \begin{cases} \begin{array}{ll} 1 & \text{if} \: k = 0 \\ \Pi_{i=1}^k p_i^{a_i + 1} & \text{if} \: k > 0 \end{array} \end{cases}\]
donde\(p_i\) está el número\(i^\text{th}\) primo.
Vamos a escribir\(\langle a_1, a_2, \ldots, a_k \rangle\) en lugar de\(\langle \left( a_1, a_2, \ldots, a_k \right) \rangle\).
Sería inútil poder codificar secuencias sin poder decodificarlas, y las siguientes funciones que definamos nos dejarán hacer eso. Pero antes de llegar ahí, necesitamos reconocer que estaremos dependiendo del Teorema Fundamental de la Aritmética, que establece que cada entero positivo mayor que uno puede expresarse exactamente de una manera (hasta el orden) como producto de primos. La prueba de este teorema (probado por primera vez por Euclides) no es trivial y está más allá del alcance de este libro, pero ciertamente vale la pena mirar hacia arriba. Pero felizmente recordaremos que el teorema es cierto, y lo usaremos libremente.
Sin embargo, hay un detalle desordenado con el que tenemos que tratar, y bien podríamos ocuparnos ahora de ello.
Nuestras funciones de decodificación tendrán que ser funciones totales, con lo que queremos decir que cada una de las funciones tendrá dominio\(\mathbb{N}\). Pero muchos números naturales no son el código de secuencias, y tenemos que averiguar cómo lidiar con esos números. Para que las definiciones que vienen surgiendo sean razonables, y para salvarnos más dificultades más adelante, comenzamos por definir el conjunto de números que son códigos.
Vamos\(C = \{ a \in \mathbb{N} | \left( \exists s \in \mathbb{N}^{< \mathbb{N}} \right) a = \langle s \rangle \}\). Llamaremos\(C\) al conjunto de números de código.
Observe que es fácil verificar si o no\(a \in C\). Todo lo que tenemos que hacer es factorizar\(a\) y ver si alguno\(a = 1\) o si\(a\) es producto de los primeros primos.
Ahora podemos llevarnos bien con la descodificación:
La función\(| \cdot | : \mathbb{N} \rightarrow \mathbb{N}\) está definida por
\[| a | = \begin{cases} \begin{array}{ll} k & \text{if} \: a \in C \: \text{and} \: a = \langle a_1, a_2, \ldots, a_k \rangle \\ 0 & \text{otherwise} \end{array} \end{cases}\]
Si\(a\) es un número de código, diremos que\(| a |\) es la longitud de\(a\).
Chafia: Ok, ¿dónde usamos el Teorema Fundamental de la Aritmética?
Observe que hemos definido la función de tal\(| \cdot |\) manera que su dominio es todo el conjunto de números naturales. Dado que muchos números naturales no serán códigos de secuencias finitas, hemos tenido que elegir cómo definiríamos nuestra función de longitud en esos números. Entonces, por definición, si\(a\) hay algún número que no sea de la forma\(p_1^{a_1 + 1} p_2^{a_2 + 1} \ldots p_k^{a_k + 1}\), entonces\(| a | = 0\). Pero no vamos a hablar de la longitud de tal número.
Por favor, tenga cuidado con la diferencia entre\(| a |\) y\(| \langle a \rangle |\). Ver Ejercicio 2.
Para cada uno\(i \in \mathbb{N}\) con\(i \geq 1\), deja\(\left( \cdot \right)_i\) ser la función con dominio\(\mathbb{N}\) y codominio\(\mathbb{N}\) definido por
\[\left( a \right)_i = \begin{cases} \begin{array}{ll} a_i & \text{if} \: a \in C \: \text{and} \: a = \langle a_1, a_2, \ldots, a_k \rangle \: \text{and} \: 1 \leq i \leq k \\ 0 & \text{otherwise} \end{array} \end{cases}\]
El lector escéptico (y de ojos agudos) habrá notado otro pequeño detalle aquí. Considera el número\(a = 10\). Hemos coincidido en que 10 no codifica una secuencia, y así lo dice la Definición 4.5.5\(| 10 | = 0\). Sin embargo, si usamos nuestra función de decodificación que acabamos de definir, tal vez buscando el séptimo término de la secuencia, y enchufamos la entrada 10, nos encontramos\(\left( 10 \right)_7 = 0\). Esto es un poco molesto, ya que el observador casual podría pensar que se supone que 10 codifica una secuencia de longitud 0, pero más allá de agravar a los autores, este efecto secundario no nos molestará en absoluto.
También necesitaremos poder juntar los códigos de dos secuencias, una tras otra, y la siguiente función nos permita hacerlo.
La función\(^\frown : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) está definida por
\[a ^\frown b = \begin{cases} \begin{array}{ll} \langle a_1, \ldots, a_k, b_1, \ldots, b_l \rangle & \text{if} \: a = \langle a_1, \ldots, a_k \rangle \: \text{and} \: b = \langle b_1, \ldots, b_l \rangle, \\ & \: \: \: \: \text{with} \: \left( a_1, \ldots a_k \right) \in \mathbb{N}^{< \mathbb{N}} \: \text{and} \\ & \: \: \: \: \left( b_1, \ldots, b_l \right) \in \mathbb{N}^{< \mathbb{N}} \\ 0 & \text{otherwise} \end{array} \end{cases}\]
Podría valer la pena trabajar a través de un ejemplo en este punto. Supongamos que quisiéramos calcular\(793800 ^\frown 73500\). Primero haríamos mucho factoring para encontrar eso\(793800 = 2^3 3^4 5^2 7^2\), entonces\(793800 = \langle 2, 3, 1, 1 \rangle\). De igual manera,\(73500 = \langle 1, 0, 2, 1 \rangle\). Entonces, por definición
\[793800 ^\frown 73500 = \langle 2, 3, 1, 1, 1, 0, 2, 1 \rangle = 2^3 3^4 5^2 7^2 11^2 13^1 17^3 19^2 = 2214592288108200,\]
mientras\(793801 ^\frown 73500 = 0\).
Las funciones introducidas anteriormente nos permiten codificar secuencias finitas y, dado un número de código\(a\), descodificarlas. En otras palabras, si\(a \in C\) y\(a = \langle a_1, \ldots, a_k \rangle\), entonces para cada\ i\) tal que\(1 \leq i \leq | a |\),\(\left( a \right)_i = a_i\).
En este punto, hemos construido todos los aparatos de codificación que necesitaremos. Ya sea que abordemos la incompletitud a través de fórmulas o a través de cálculos, podremos codificar y decodificar los objetos y secuencias de los objetos. Hemos construido la infraestructura. En los Capítulos 5 y 6 aplicaremos la codificación a las fórmulas, mientras que en el Capítulo 7 utilizaremos la codificación en los cálculos. Ambas rutas nos llevan a la incompletitud.
Ejercicios
- Calcular lo siguiente:
(a)\(\langle 3, 0, 4, 2, 1 \rangle\)
(b)\(\left( 16910355000 \right)_3\)
(c)\(| 16910355000 |\)
(d)\(\left( 16910355000 \right)_{42}\)
(e)\(\langle 2, 7, 1, 8 \rangle ^\frown \langle 2, 8, 1 \rangle\)
(f)\(17 ^\frown 42\) - Encontrar un número\(a\) tal que\(| a | \neq | \langle a \rangle |\) o probar que no\(a\) existe tal. Entonces encuentra un número\(b\) tal que\(| b | = | \langle b \rangle |\) o demuestre que no\(b\) existe tal.