5.5: Codificación - Naïvely
- Page ID
- 113549
Si conoces a un niño de cierta edad, sin duda te has topado con mensajes codificados del formulario
\[1 \: 14 \: \: \: 1 \: 16 \: 16 \: 12 \: 5 \: \: \: 1 \: \: \: 4 \: 1 \: 25\]
donde las letras están codificadas por números asociados con su lugar en el alfabeto. Si ignoramos los espacios anteriores, podemos pensar en la frase como codificada por un solo número, y ese número puede tener propiedades especiales. Por ejemplo, el código anterior no es primo y es divisible por exactamente cinco primos distintos. Si queremos, podríamos decir que la codificación nos permite afirmar las mismas afirmaciones sobre la frase que se ha codificado. Por ejemplo, si tomamos la frase
El código para esta frase es par
y lo codificó como un número, podrías notar que el código termina en 4, así que podrías tener la tentación de decir que la frase era correcta en lo que afirma.
Lo que estamos haciendo aquí es representar declaraciones en inglés como números, e investigar las propiedades de los números. Podemos hacer lo mismo con declaraciones de\(\mathcal{L}_{NT}\). Por ejemplo, si tomamos la frase
\[= 0S0,\]
tal vez podríamos codificar esta frase como el número
\[1042492561137562500000000,\]
y luego podemos afirmar cosas sobre el número asociado con la cadena. Por ejemplo, el código para\(= 0S0\) es un elemento del conjunto de números que son divisibles por 10, y está en el conjunto de números que son mayores que la deuda nacional. Lo que hará que todo esto sea interesante es que preguntamos si el código para\(= 0S0\) es un elemento del conjunto de todos los códigos de oraciones de los que se pueden deducir\(N\). Entonces estaremos preguntando si nuestra sentencia es un teorema de\(N\). Si lo es, entonces sabremos que\(N\) es inconsistente. Si no lo es, entonces\(N\) es consistente. Así habremos reducido la cuestión de la consistencia de\(N\) a una pregunta sobre números y conjuntos!
Esta es la perspicacia que llevó a Gödel al Teorema de la Incompletitud. Dado cualquier conjunto razonable de axiomas\(A\), Gödel mostró una manera de codificar la frase
Esta frase no es un teorema de\(A\)
como sentencia de\(\mathcal{L}_{NT}\) y acreditar que esta sentencia no puede estar en el conjunto de sentencias que sean probables de\(A\). Por lo que encontró una frase que era cierta, pero no demostrable. Nosotros, en este capítulo y en el siguiente, haremos lo mismo.
Pero primero, tendremos que establecer nuestro mecanismo de codificación. En esta sección no desarrollaremos nuestra codificación oficial, sino más bien, una versión simplificada para darte una muestra de las cosas por venir. Describamos el sistema que usamos para el ejemplo anterior.
Comenzamos asignando números de símbolo a los símbolos de\(\mathcal{L}_{NT}\), como se da en la Tabla 5.1. Observe que los números de símbolo solo se asignan para los elementos oficiales del idioma, por lo que si necesita utilizar alguna abreviación\(\exists\), como\(\rightarrow\) o, deberá escribirlos en términos de sus definiciones.
\[\begin{array}{||c|c||c|c||} \hline \text{Symbol} & \text{Symbol Number} & \text{Symbol} & \text{Symbol Number} \\ \hline \neg & 1 & + & 13 \\ \lor & 3 & \cdot & 15 \\ \forall & 5 & E & 17 \\ = & 7 & < & 19 \\ 0 & 9 & ( & 21 \\ S & 11 & ) & 23 \\ & & v_i & 2i \\ \hline \end{array}\]
Tabla 5.1: Números de símbolo para\(\mathcal{L}_{NT}\)
Entonces tuvimos que encontrar una manera de codificar secuencias de símbolos. La idea aquí es bastante simple, ya que solo tomaremos los números de símbolo y los codificaremos usando el esquema que describimos en la Sección 4.5. Por ejemplo, si nos fijamos en la secuencia
\[= 0S0\]
la secuencia de los números de símbolo que esto genera es
\[\left( 7, 9, 11, 9 \right),\]
así que el código para la secuencia sería (recuerda que agregamos uno al exponente cuando codificamos secuencias de números)
\[2^8 3^{10} 5^{12} 7^{10},\]
que también se conoce como
\[1042492561137562500000000,\]
el ejemplo que vimos antes.
Observe que nuestra codificación es efectiva, en el sentido de que es fácil, dado un número, encontrar su factorización y así encontrar la cadena que está codificada por el número.
Chaf: La palabra fácil se usa aquí en su sentido matemático, no en su sentido de la informática. En realidad puede tomar muchísimo tiempo factorizar muchos números, especialmente números del tamaño que vamos a discutir.
Ahora bien, el problema con todo esto no es que le resultaría difícil reconocer números de código, o decodificar un número dado, o algo así. Más bien, lo que resulta complicado es demostrar que\(N\), nuestra colección de axiomas, es lo suficientemente fuerte como para poder probar verdaderas aseveraciones sobre los números. Por ejemplo, nos\(N\) gustaría poder demostrar que el término
\[\overline{1042492561137562500000000}\]
representa un número que es el código\(\mathcal{L}_{NT}\) de una frase. Los detalles de mostrar que\(N\) tiene esta fortaleza nos ocuparán para las próximas varias secciones.
Ejercicio
- Decodificar el mensaje que inicia esta sección.
- Codifique las siguientes\(\mathcal{L}_{NT}\) fórmulas utilizando el método descrito en esta sección y en la Sección 4.5.
a\(= + 000\)
) b\(= E v_1 S v_2 \cdot E v_1 v_2 v_1\)
) c\(\left( = 00 \lor \left( \neg < 00 \right) \right)\)
) d\(\left( \exists v_2 \right) \left( < v_2 0 \right)\) - Encuentra la\(\mathcal{L}_{NT}\) _fórmula que está representada por los siguientes números. Una calculadora (o un sistema de álgebra computacional) será útil. Escribe tu respuesta en una forma que la gente normal pueda entender - gente normal con cierta familiaridad con la lógica de primer orden y las matemáticas, es decir.
(a)\(773190132422400000000000000\)
(b)\(29986008216169640502067200000000\)
(c)\(2^{22} 3^6 5^7 7^{24} 11^{22} 13^8 17^7 19^{10} 23^{24}\)