En matemáticas , una numeración de Gödel para secuencias proporciona una forma eficaz de representar cada secuencia finita de números naturales como un solo número natural. Si bien una incrustación teórica de conjuntos es seguramente posible, el énfasis está en la efectividad de las funciones que manipulan tales representaciones de secuencias: las operaciones en secuencias (acceso a miembros individuales, concatenación) pueden ser "implementadas" usando funciones recursivas totales , y de hecho por primitivas funciones recursivas .
Por lo general, se utiliza para construir " tipos de datos " secuenciales en formalizaciones basadas en aritmética de algunas nociones fundamentales de las matemáticas. Es un caso específico de la idea más general de la numeración de Gödel . Por ejemplo, la teoría de funciones recursivas se puede considerar como una formalización de la noción de un algoritmo y se puede considerar como un lenguaje de programación para imitar listas codificando una secuencia de números naturales en un solo número natural. [1] [2]
Numeración de Gödel
Además de usar la numeración de Gödel para codificar secuencias únicas de símbolos en números naturales únicos (es decir, colocar números en correspondencia mutuamente excluyente o uno a uno con las secuencias), podemos usarla para codificar “arquitecturas” completas de “máquinas” sofisticadas. Por ejemplo, podemos codificar los algoritmos de Markov , [3] o las máquinas de Turing [4] en números naturales y así demostrar que el poder expresivo de la teoría de funciones recursivas no es menor que el de las antiguas formalizaciones de algoritmos tipo máquina.
Acceso a miembros
Cualquier representación de secuencias debe contener toda la información como en la secuencia original; lo más importante es que cada miembro individual debe ser recuperable. Sin embargo, la longitud no tiene por qué coincidir directamente; incluso si queremos manejar secuencias de diferente longitud, podemos almacenar datos de longitud como un miembro excedente, [5] o como el otro miembro de un par ordenado usando una función de emparejamiento .
Esperamos que exista una forma eficaz para este proceso de recuperación de información en forma de una función recursiva total apropiada. Queremos encontrar una función f totalmente recursiva con la propiedad de que para todo n y para cualquier secuencia de n números naturales, existe un número natural apropiado a , llamado número de Gödel de la secuencia, tal que para todo i donde, .
Hay funciones efectivas que pueden recuperar cada miembro de la secuencia original a partir de un número de Gödel de la secuencia. Además, podemos definir algunos de ellos de forma constructiva , por lo que podemos ir mucho más allá de las meras pruebas de existencia .
Lema de la función β de Gödel
Mediante un uso ingenioso del teorema del resto chino , podemos definir constructivamente una función recursiva de este tipo.(utilizando funciones teóricas numéricas simples, todas las cuales se pueden definir de forma recursiva total) cumpliendo las especificaciones dadas anteriormente. Gödel definió elfunción utilizando el teorema del resto chino en su artículo escrito en 1931. Esta es una función recursiva primitiva . [6]
Por lo tanto, para todo n y para cualquier secuencia de n- longitudes de números naturales, existe un número natural apropiado a , llamado número de Gödel de la secuencia tal que. [7]
Usar una función de emparejamiento
Nuestra solución específica dependerá de una función de emparejamiento; hay varias formas de implementar la función de emparejamiento, por lo que se debe seleccionar un método. Ahora, podemos abstraernos de los detalles de la implementación de la función de emparejamiento. Solo necesitamos conocer su " interfaz ": deje, K y L denotan la función de emparejamiento y sus dos funciones de proyección , respectivamente, satisfaciendo la especificación
No discutiremos ni formalizaremos aquí el axioma para excluir objetos extraños, ya que no es necesario para comprender el método.
Resto de números naturales
Usaremos otra función auxiliar que calculará el resto de los números naturales . Ejemplos:
Se puede demostrar que esta función se puede implementar como una función recursiva.
Usando el teorema del resto chino
Implementación de la función β
Usando el teorema del resto chino , podemos probar que la implementación como
funcionará, de acuerdo con la especificación que esperamos satisfacer. Podemos usar una forma más concisa mediante un abuso de notación (que constituye una especie de coincidencia de patrones ):
Logremos aún más legibilidad mediante más modularidad y reutilización (ya que estas nociones se utilizan en informática [8] ): definiendo la secuencia , podemos escribir
- .
Usaremos esto notación en la prueba.
Supuestos ajustados a mano
Para probar la exactitud de la definición anterior de la función, usaremos varios lemas. Estos tienen sus propias suposiciones. Ahora tratamos de descubrir estas suposiciones, calibrando y ajustando su fuerza con cuidado: no deben decirse en una forma superfluamente aguda o insatisfactoriamente débil.
Dejar ser una secuencia de números naturales. Sea m elegido para satisfacer
La primera suposición se entiende como
Es necesario para cumplir con un supuesto del teorema del resto chino (el de ser coprime por pares ). En la literatura, a veces este requisito se reemplaza por uno más fuerte, por ejemplo construido de manera constructiva con la función factorial , [1] pero la premisa más fuerte no es necesaria para esta prueba. [2]
El segundo supuesto no concierne al teorema del resto chino de ninguna manera. Tendrá importancia para demostrar que la especificación parase cumple eventualmente. Asegura que un solución del sistema de congruencia simultánea
- para cada i donde
también satisface
Una suposición más fuerte para m que requiere satisface automáticamente la segunda suposición (si definimos la notación como anteriormente).
Prueba de que se cumple el supuesto (de coprimalidad) del teorema del resto chino
En la sección Supuestos ajustados a mano , solicitamos que
- . Lo que queremos demostrar es que podemos producir una secuencia de números coprimos por pares de una manera que resultará corresponder a la implementación de la función β .
En detalle:
recordando eso nosotros definimos .
La prueba es por contradiccion; asumir la negación del enunciado original:
Primeros pasos
Sabemos lo que significa relación “coprime” (afortunadamente, su negación se puede formular de forma concisa); así, sustituyamos de la forma adecuada:
Usando una forma normal de prenex "más" (pero tenga en cuenta que permite una notación similar a una restricción en los cuantificadores):
Debido a un teorema sobre divisibilidad , nos permite también decir
- .
Sustituyendo las definiciones de-notación de secuencia, obtenemos , así (como los axiomas de igualdad postulan que la identidad es una relación de congruencia [10] ) obtenemos
- .
Como p es un elemento primo (tenga en cuenta que se usa la propiedad del elemento irreducible ), obtenemos
- .
Recurriendo a la primera suposición ajustada a mano
Ahora debemos recurrir a nuestra suposición
- .
La suposición se eligió cuidadosamente para que fuera lo más débil posible, pero lo suficientemente fuerte como para permitirnos usarla ahora.
La negación asumida del enunciado original contiene un enunciado existencial apropiado usando índices ; esto implica, por lo que se puede aplicar el supuesto mencionado, por lo que sostiene.
Usar un teorema (de objeto) del cálculo proposicional como lema
Podemos probar por varios medios [11] conocidos en cálculo proposicional que
sostiene.
Desde , por la propiedad de transitividad de la relación de divisibilidad ,. Así (como los axiomas de igualdad postulan que la identidad es una relación de congruencia [10] )
puede ser probado.
Alcanzando la contradicción
La negación de la declaración original contenía
y acabamos de probar
- .
Por lo tanto,
también debe aguantar. Pero después de sustituir la definición de,
Así, resumiendo las tres afirmaciones anteriores, por transitividad de la igualdad ,
también debe aguantar.
Sin embargo, en la negación del enunciado original, p se cuantifica existencialmente y se restringe a números primos.. Esto establece la contradicción a la que queríamos llegar.
Fin de la reducción ad absurdum
Al llegar a la contradicción con su negación, acabamos de probar la declaración original:
El sistema de congruencias simultáneas
Construimos un sistema de congruencias simultáneas
Podemos escribirlo de una manera más concisa:
Muchas declaraciones se dirán a continuación, todas comenzando con "". Para lograr un tratamiento más ergonómico, a partir de ahora todas las declaraciones deben leerse como en el ámbito de una cuantificación. Por lo tanto, comienza aquí.
Elijamos una solución para el sistema de congruencias simultáneas. Debe existir al menos una solución, porqueson comprime por pares como se demostró en las secciones anteriores, por lo que podemos referirnos a la solución asegurada por el teorema del resto chino. Así, a partir de ahora podemos considerar tan satisfactorio
- ,
lo que significa (por definición de aritmética modular ) que
Recurriendo a la suposición de segunda mano afinada
Recuerde la segunda suposición, "”, Y recuerde que ahora estamos en el alcance de una cuantificación implícita para i , por lo que no repetimos su cuantificación para cada declaración.
La segunda suposición implica que
- .
Ahora por transitividad de la igualdad obtenemos
- .
QED
Nuestro objetivo original era demostrar que la definición
es bueno para lograr lo que declaramos en la especificación de : queremos sostener.
Esto puede verse ahora por la transitividad de la igualdad , observando las tres ecuaciones anteriores.
(El gran alcance de i termina aquí).
Existencia y singularidad
Acabamos de demostrar la exactitud de la definición de : su especificación requiere
se cumple. Aunque demostrar esto fue lo más importante para establecer un esquema de codificación para secuencias, todavía tenemos que llenar algunos vacíos. Estas son nociones relacionadas similares a la existencia y la unicidad (aunque en la unicidad, aquí debe entenderse "como mucho uno", y la conjunción de ambos se retrasa como resultado final).
Singularidad de la codificación, lograda mediante la minimalización
Nuestra pregunta final es: ¿qué número debe representar la codificación de secuencia ? La especificación declara solo una cuantificación existencial, aún no una conexión funcional. Queremos una conexión constructiva y algorítmica: una función recursiva (total) que realiza la codificación.
Totalidad, porque la minimalización se restringe a funciones especiales
Este vacío se puede llenar de una manera sencilla: usaremos la minimalización , y la totalidad de la función resultante está asegurada por todo lo que hemos probado hasta ahora (es decir, la exactitud de la definición decumpliendo su especificación). De hecho, la especificación
juega aquí un papel de una noción más general ("función especial" [12] ). La importancia de esta noción es que nos permite separar la (sub) clase de funciones recursivas (totales) de la (super) clase de funciones recursivas parciales. En resumen, la especificación dice que una función f [13] que satisface la especificación
es una función especial; es decir, para cada combinación fija de todos los argumentos excepto el último, la función f tiene raíz en su último argumento:
La función de numeración de Gödel g se puede elegir para que sea recursiva total
Por lo tanto, escojamos el número mínimo posible que se ajuste bien a la especificación de la función: [5]
- .
Se puede probar (utilizando las nociones de la sección anterior) que g es (total) recursiva.
Acceso de longitud
Si usamos el esquema anterior para codificar secuencias solo en contextos donde la longitud de las secuencias es fija, entonces no surge ningún problema. En otras palabras, podemos usarlos de manera análoga a como se usan los arreglos en la programación.
Pero a veces necesitamos secuencias de estiramiento dinámico o tenemos que tratar con secuencias cuya longitud no se puede escribir de forma estática. En otras palabras, podemos codificar secuencias de forma análoga a las listas en la programación.
Para ilustrar ambos casos: si formamos la numeración de Gödel de una máquina de Turing, entonces cada fila en la matriz del "programa" se puede representar con tuplas, secuencias de longitud fija (por lo tanto, sin almacenar la longitud), porque el número de las columnas es fijo. [14] Pero si queremos razonar sobre cosas similares a configuraciones (de máquinas de Turing), y específicamente si queremos codificar la parte significativa de la cinta de una máquina de Turing en funcionamiento, entonces tenemos que representar secuencias junto con su longitud. . Podemos imitar secuencias de estiramiento dinámico representando la concatenación de secuencias (o al menos, aumentando una secuencia con un elemento más) con una función totalmente recursiva. [15]
La longitud se puede almacenar simplemente como miembro excedente: [5]
- .
La correspondiente modificación de la prueba es sencilla, agregando un excedente
al sistema de congruencias simultáneas (siempre que el índice de miembros excedentes sea 0). Además, los supuestos deben modificarse en consecuencia.
Notas
- ↑ a b Monk, 1976 : 56–58
- ^ a b Csirmaz 1994 : 99–100 (ver en línea )
- ↑ Monk, 1976 : 72–74.
- ↑ Monk, 1976 : 52–55.
- ^ a b c d Csirmaz 1994 : 100 (ver en línea )
- ↑ Smullyan 2003 : 56 (= Capítulo IV, § 5, nota 1)
- ↑ Monk 1976 : 58 (= Thm 3.46)
- ^ Hughes 1989 (ver en línea Archivado 2006-12-08 en Wayback Machine )
- ^ Burris 1998 : Texto complementario, Aritmética I , Lema 4
- ^ a b ver también nociones relacionadas, por ejemplo, "iguales por iguales" ( transparencia referencial ), y otra noción relacionada Ley / identidad de los indiscernibles de Leibniz
- ^ prueba teórica (pasos algebraicos); o semántica ( tabla de verdad , método de cuadros analíticos , diagrama de Venn , diagrama de Veitch / mapa de Karnaugh )
- ↑ Monk 1976 : 45 (= Def 3.1.)
- ^ Por ejemplo, definido por
- ↑ Monk 1976 : 53 (= Def 3.20, Lem 3.21)
- ^ Csirmaz 1994 : 101 (= Thm 10.7, Conseq 10.8), ver en línea
Referencias
- Burris, Stanley N. (1998). "Texto complementario, Aritmética I" . Lógica para las matemáticas y la informática . Prentice Hall. ISBN 978-0-13-285974-5.
- Csirmaz, László; Hajnal, András (1994). "Rekurzív függvények" . Matematikai logika (postscript + gzip)
|format=
requiere|url=
( ayuda ) (en húngaro). Budapest: Universidad Eötvös Loránd.Cada capítulo se puede descargar literalmente en la página del autor . - Hughes, John (1989). "Por qué importa la programación funcional" . Revista informática . 32 (2): 98-107. doi : 10.1093 / comjnl / 32.2.98 . Archivado desde el original el 8 de diciembre de 2006.
- Monk, J. Donald (1976). Lógica matemática . Textos de Posgrado en Matemáticas. Nueva York • Heidelberg • Berlín: Springer-Verlag.
- Smullyan, Raymond Merrill (1992). Teoremas de incompletitud de Gödel . Prensa de la Universidad de Oxford. ISBN 978-0-19-504672-4.
- Smullyan, Raymond Merrill (2003). Gödel nemteljességi tételei (en húngaro). Budapest: Typotex. ISBN 978-963-9326-99-6.Traducción de Smullyan 1992 .
enlaces externos
- Burris, Stanley N. (1998). "Texto complementario, Aritmética I" . Lógica para las matemáticas y la informática . Prentice Hall. ISBN 978-0-13-285974-5.