Algunos registros sobre conjuntos contables recursivos y conjuntos Diofanto
Además, he visto discusiones relacionadas antes cuando leí "Eternal Turing". Aquí registraré algunas ideas sobre Diofanto y los conjuntos contables recursivos.
Para entender los conjuntos recursivamente enumerables, primero debemos entender las máquinas de Turing.
Para conocer la definición de máquina de Turing, puedes consultar Wikipedia.
Personalmente prefiero esta definición, aunque no es obligatoria:
Obviamente, el rol de es descripción y el rol de es configuración. El primero describe la "cinta de papel" y el segundo describe el estado actual de las máquinas de Turing.
Por lo tanto, el proceso de operación de la máquina de Turing puede considerarse como colocar un punto de Turing en una posición inicial dada en el espacio de Turing en un estado inicial y hacerlo moverse nuevamente, "liberando la" línea del mundo ". generado por "Move" tiene en última instancia tres posibilidades:
Por supuesto, esta afirmación no tiene mucho sentido, pero parece "hermosa".
Si finalmente se acepta la máquina de Turing (por supuesto que se detiene), entonces su espacio de Turing se denomina "resultado de salida" y, en consecuencia, el espacio de Turing inicial se denomina "parámetro de entrada".
Entonces, si solo te concentras en el principio y el final de la pintura, la máquina de Turing es así: es decir, es una función parcial que asigna los parámetros de entrada al resultado de salida. disparates.
Si limitamos el estado en el espacio de Turing al conjunto potencia de un conjunto finito de símbolos no vacío, entonces la máquina de Turing obviamente puede considerarse como una función parcial que puede asignar lo finito a otro conjunto finito, es decir:
Aquí está el conjunto de todos los estados de entrada aceptables de la máquina de Turing. Si un estado de entrada no existe, la máquina de Turing puede rechazarlo y detenerse, o puede que nunca se detenga.
Aquí, el conjunto de estados de entrada aceptables de una máquina de Turing se denomina "conjunto enumerable ergódico".
De manera similar, si un conjunto se llama "enumerable ergódico", significa que existe una máquina de Turing tal que es exactamente el conjunto de todos los estados de entrada aceptables.
El problema del tiempo de parada indeterminado nos dice que nunca encontraremos una máquina de Turing universal que pueda decirnos si cualquier máquina de Turing puede detenerse en un estado de entrada determinado.
En otras palabras, es imposible para nosotros encontrar una máquina de Turing universal que pueda determinar si cualquier estado de entrada es un estado de entrada aceptable para una máquina de Turing.
Por lo tanto, esto equivale a decir que no existe una máquina de Turing universal que pueda ayudarnos a determinar si un conjunto es transitable y enumerable.
Por otro lado, veamos la serie de Diofanto.
Si la suma de los coeficientes son números enteros, entonces todas las ecuaciones de forma se denominan "ecuaciones diofánticas". Por ejemplo, nuestra ecuación cuadrática más común es la ecuación diofántica; la ecuación de Fermat también es una ecuación diofántica y sabemos que esta ecuación no tiene solución entera.
La existencia de raíces enteras de la ecuación diofántica es un problema muy interesante y difícil. Por ejemplo, la ecuación de Fermat existe sin raíces enteras.
Entonces, es una pregunta muy interesante si existe un algoritmo que pueda determinar automáticamente si cualquier ecuación diofántica de entrada tiene una solución entera. De ser así, muchos problemas, incluido el último teorema de Fermat, serían fácilmente solucionables.
Ahora, extraemos todos los coeficientes de una ecuación diofántica: siempre hay un parámetro.
A continuación, arreglaremos algunos de estos parámetros (o ninguno) y la otra parte será variable (solo números enteros). Un conjunto de tales parámetros variables se denomina "grupo de parámetros". El conjunto de todos los conjuntos de parámetros que permiten que una ecuación diofántica tenga soluciones enteras se denomina conjunto diofántico de la ecuación diofántica.
En otras palabras, cualquier elemento del conjunto diofántico puede garantizar que la ecuación diofántica correspondiente (incluidos aquellos parámetros enteros fijos) debe tener una solución entera; de lo contrario, la ecuación diofántica no tiene solución entera.
Si existe una correspondencia uno a uno entre el conjunto de Diofanto y el recorrido del conjunto contable, significa que la máquina de Turing no puede determinar al menos un conjunto de Diofanto, porque el recorrido del El conjunto contable es indecidible, lo que significa que la máquina de Turing no puede determinar al menos una ecuación diofántica (todos los parámetros son fijos).
Esto equivale a decir que la respuesta a la décima pregunta de Hilbert es no.
La gente ha trabajado duro durante mucho tiempo para demostrar (y refutar) el décimo problema de Hilbert.
Davis, Putnam y Julia Robinson, la primera matemática elegida para la Academia Nacional de Ciencias de Estados Unidos, trabajaron juntos durante mucho tiempo para demostrar finalmente esto:
Demuestra la última conjetura, Jr.' s Estaba el matemático ruso Yuri Machiavelovich.
Así, cuatro personas unieron fuerzas para demostrar que el conjunto de Diofanto equivale a atravesar el conjunto enumerable.
Esto se llama teorema MRDP, también conocido como teorema de Maquiavelo.
Ahora que terminó la introducción histórica, hablemos de mis pensamientos personales.
Este teorema es muy interesante. Nos dice dos cosas:
¿Lo has descubierto?
Lo interesante aquí es que la ecuación diofántica es obviamente continuamente diferenciable (aunque el conjunto diofántico no tiene nada que ver con las variables independientes de la función correspondiente de la ecuación), y la máquina de Turing es una ecuación muy obvia. objeto discreto. Estas dos cosas, que a primera vista parecen completamente diferentes, tienen una conexión interior maravillosa.
Y, lo que es más importante, en nuestra impresión, las máquinas de Turing pueden hacer todo lo que las ecuaciones y funciones pueden hacer; pero es posible que las ecuaciones y funciones no necesariamente puedan hacer todo lo que las máquinas de Turing pueden hacer. Parece extraño que estas dos cosas "funcionalmente desiguales" tengan los mismos requisitos de parámetros de entrada.
Sin embargo, pensándolo bien, parece necesario. Después de todo, hay tantas ecuaciones diofánticas como máquinas de Turing, y ambas son Alef 0, por lo que parece normal tener esa relación de mapeo.
De hecho, la razón por la que se utilizan los parámetros de la función diofántica en lugar de variables de entrada para corresponder al estado de entrada de la máquina de Turing es porque para funciones polinómicas como la función diofántica, siempre que la la variable de entrada no es infinita, siempre puede dar una salida entera, pero si los coeficientes no son apropiados, es posible que la ecuación no encuentre una solución entera. Por lo tanto, parece razonable usar parámetros en lugar de variables para corresponder; incluso podemos "adivinar" que esas soluciones enteras pueden usar el estado interno o incluso la salida del tipo correspondiente de máquina de Turing hasta cierto punto, quién sabe.
Incluso supongo que para cualquier máquina de Turing que asigne datos de entrada A a datos de salida B, bajo cualquier regla de codificación (asignación de datos a números naturales), se puede encontrar al menos un conjunto de funciones diofánticas (coeficiente entero polinomio) corresponde a uno a uno. Hay B conjuntos de funciones diofánticas, cada conjunto tiene una variable de entrada independiente.
Pero entonces pienso que tal mapeo isomórfico no debería existir, porque en primer lugar, cualquier grupo de funciones diofánticas debe ser mapeado a un tipo de máquina de Turing, y las características de este tipo de función diofántica son puede generar de forma única un número entero para cualquier entrada, lo que significa que la máquina de Turing correspondiente a cada grupo de funciones diofánticas debe poder detenerse en el estado de aceptación para cualquier entrada, pero esto obviamente no es algo que cualquier máquina de Turing pueda satisfacer. de modo que debe haber una máquina de Turing que no pueda estar tan satisfecha.
Así que aquí se refleja nuevamente la ventaja de utilizar los parámetros de la función diofántica para que se correspondan con la entrada de la máquina de Turing.
Bien, en lugar de insistir en las sorpresas que genera esta conexión intrínseca, es mejor considerar esta pregunta:
¿Se pueden ampliar estos dos conjuntos?
Específicamente, en la aproximación diofántica, ya no requerimos que los parámetros de la ecuación diofántica sean números enteros, sino que pueden ser cualquier número real. De esta manera, todos los subconjuntos de coeficientes reales que permiten que una ecuación diofántica tenga una solución entera son el "conjunto diofántico extendido" de la ecuación diofántica.
Por ejemplo, el conjunto diofántico de esta ecuación diofántica es:
Su conjunto diofántico extendido puede ser:
Obviamente mucho más grande, el primero es solo un subconjunto de este último.
Sin embargo, tal expansión no parece lo suficientemente “salvaje”. Echemos un vistazo a lo siguiente:
Es un funcional llamado funcional diofántico, en el que la suma de funciones se llama función de parámetro, y la función es una función de prueba, que se requiere que sea una cualquier conjunto de un número real se denomina "dominio restringido" y cualquier subconjunto de otro número real se denomina "dominio activo". Suponiendo que la ecuación existe y es cierta, entonces el grupo binario se denomina "grupo de parámetros universal" del "grupo de problemas diofánticos". El conjunto de todos los conjuntos de parámetros universales es el "conjunto diofántico universal" de este funcional diofántico.
Tenga en cuenta que aquí no es necesario que las funciones , y sean suaves o incluso continuas, por lo que pueden ser funciones por partes. No existen requisitos para el dominio activo y el dominio restringido. Puede ser un conjunto contable, un conjunto discreto (en ambos casos la integral se convierte en una suma) o un conjunto de Hausdorff. Generalmente podemos discutir el Atlas Pan Diofanto en términos de dominios activos fijos y dominios restringidos.
Obviamente, cuando , el conjunto diofántico universal es un superconjunto del conjunto diofántico extendido y del conjunto diofántico mencionados anteriormente.
O, más formalmente:
Dado que la expansión del Atlas Diofántico es desenfrenada, ¿qué pasa con la expansión de los conjuntos contables transversales?
O, más exactamente, podemos preguntar aquí cómo reproducir la extensión de la máquina de Turing.
En la definición anterior de máquina de Turing, existen varios conjuntos discretos:
¿Qué pasa si estos dos conjuntos son generalizados?
Así:
Con cualquier espacio como espacio base, cualquier elemento en el espacio base generará directamente un espacio propio (sin discreción ni finitud), que se denomina "espacio externo". . Luego, hay una "partícula" en la tabla, que corresponde a un elemento de la tabla, llamado "posición". También existe un "estado interno" cuyos valores están en el "espacio de estados interno".
Ahora, no es necesario que el espacio inferior, el espacio de estados externo y el espacio de estados interno sean discretos o finitos, y pueden ser cualquier conjunto.
En realidad, esto es una especie de haz de fibras, pero es diferente.
La regla de transferencia sigue siendo la misma que se mencionó anteriormente. Primero cambie el estado externo de la posición de la partícula, luego cambie el estado interno de la partícula y luego mueva la partícula a una nueva posición. Funciona un poco como una conexión en geometría diferencial, pero no requerimos que este movimiento solo pueda moverse en posiciones adyacentes, por lo que se puede decir que es un problema cinemático en el haz de fibras con una estructura de agujero de gusano agregada. Por supuesto, también podemos limitar el cambio de posición aquí para que solo se mueva dentro de la vecindad del punto actual, al igual que el cabezal de lectura y escritura en una máquina de Turing estándar solo puede mover una cuadrícula de izquierda a derecha, lo que se parece más a una cinemática. Al mismo tiempo, los cambios en los estados internos y externos se parecen más al trabajo de la comunicación maestro-esclavo y la comunicación múltiple subyacente.
Una vez que la línea mundial de una partícula ingresa a la región "indefinida", es rechazada y detenida, comparable a la singularidad de caer en un agujero negro.
También es posible que las partículas se muevan a una región específica en el colector inferior, sean aceptadas y detenidas, una metáfora que podría compararse con cerrar el universo a su fatídico final.
También es posible que la línea mundial de partículas nunca se detenga y siempre gire en un área determinada, comparable al universo abierto que nunca termina.
El estado inicial de esta súper máquina de Turing, es decir, el estado inicial del colector inferior, se puede comparar con el estado del universo en el Big Bang.
Bueno, en comparación con la clasificación por analogía, el espacio-tiempo ciertamente no es una súper máquina de Turing según esta definición; probablemente no.
Ahora bien, el estado de entrada (y el estado de salida) de esta súper máquina de Turing no es un conjunto discreto.
Si se trata de un espacio continuo, como una variedad diferencial, entonces el estado de entrada puede ser una curva o superficie en el gráfico. Los estados externos de los puntos fuera de esta curva o superficie son todos 0, y los estados externos de los puntos en esta curva o superficie constituyen el estado de entrada.
Entonces, está claro que, en teoría, puede haber una correspondencia entre el Atlas Pan-Diophantus y los estados de entrada que son aceptables aquí.
Entonces, aquí viene la pregunta:
¿Existe siempre una correspondencia uno a uno entre los estados iniciales aceptables de cualquiera de las máquinas extendidas de Super-Turing mencionadas anteriormente y un Pan Diofanto? ¿Atlas?
Si lo piensas bien, es así:
¿Existe siempre una correspondencia uno a uno entre el estado inicial de un universo cerrado bajo alguna regla física y el conjunto? de Pan Diofanto?
Esta idea es más desenfrenada: aunque es más bella, no tiene ningún significado práctico.
Bromas aparte, el problema todavía existe.
Ampliamos el Atlas Diofántico y la máquina de Turing respectivamente para hacerlos lo más "continuos" posible, y luego preguntamos si existe una brecha entre el Atlas Diofántico universal correspondiente y el conjunto identificable de Super-Turing. correspondencia, como entre el conjunto diofántico y el conjunto identificable por Turing.
Por supuesto, no puedo responder a esta pregunta ahora.
Veamos algo más.
Por ejemplo, la compresibilidad.
En el campo de las máquinas de Turing, la compresibilidad está relacionada con la complejidad del algoritmo, de la siguiente manera:
Aquí separamos deliberadamente la máquina de Turing de sus parámetros de entrada. La definición de complejidad K para cualquier cadena S se proporciona arriba. Si es menor que, entonces decimos que S es compresible.
Ahora, intentemos trasplantar el problema a una Super Máquina de Turing (HTM).
A esta función la llamamos función de estado de la súper máquina de Turing.
La función de estado antes de comenzar la operación se llama estado inicial, que es el estado de entrada aceptado por la súper máquina de Turing. Un elemento en la tabla se llama "posición inicial", lo que significa que la "partícula" representa la lectura y escritura. La cabeza se moverá desde la posición inicial. Si la partícula finalmente se mueve a la "posición final" especificada, significa que la máquina de Super Turing se detiene en el estado de aceptación, y la función de estado en este momento se denomina estado final.
Entonces, detenerse en la reconocida súper máquina de Turing es mapear:.
A continuación, podemos definir una función de energía, que define la energía de un estado:
Por otro lado, la función de transferencia en sí también se puede codificar. Aunque aún no se sabe cómo codificarlo específicamente, se puede escribir formalmente, de modo que su energía se pueda calcular de la siguiente manera:
Podemos tomar la energía de la regla de transferencia de una súper máquina de Turing como la energía de esta súper máquina de Turing, de modo que podemos definir formalmente "complejidad algorítmica":
Si este es el caso, entonces decimos que la función de estado es comprimible.
Desde el punto de vista de la analogía, un estado compresible significa un estado en el que la energía se puede reducir aún más, lo que en realidad corresponde a un estado en el que la entropía se puede aumentar aún más. Por lo tanto, en este sistema, la "entropía termodinámica" y la entropía de la información de la máquina de Super-Turing deberían ser equivalentes, y el estado incompresible es la "radiación de cuerpo negro".
Por supuesto, como dije antes, esta analogía sólo es adecuada para la imaginación y tiene poca importancia práctica.
Alternativamente, también podemos considerar la incompresibilidad desde un punto de vista algebraico, tal como la idea de 10 tragos y 30 acciones:
Si la siguiente relación se cumple para un determinado conjunto de funciones, entonces se dice que el conjunto de funciones es comprimible en el mundo:
Es decir, al menos una función permite que cualquier elemento de datos se derive de otros datos en el conjunto dado. Registraremos esta relación como .
De hecho, esta forma de datos es muy común. Por ejemplo, si elegimos un espacio vectorial D-dimensional, solo hay una suma de vectores en el conjunto de funciones, y el conjunto de datos toma D vectores base de este espacio vectorial D-dimensional. Dado que obviamente son linealmente independientes entre sí, este conjunto de datos no se puede comprimir en el conjunto de suma de vectores.
Por supuesto, hay muchas colecciones comprimibles. Por ejemplo, ahora usamos la suma y la multiplicación de vectores para reemplazar la función establecida en la partícula anterior. Solo se necesitan dos vectores base. El tercer vector base se puede obtener mediante la multiplicación externa de estos dos vectores base, por lo que se puede comprimir. .
Por supuesto, el problema puede ser más complicado: suponiendo que el conjunto de datos es incompresible en el conjunto de funciones, pero si se agrega el conjunto de datos, el conjunto se puede comprimir en la tabla, entonces esta situación es muy interesante .
Podemos construir una función como esta:
Entonces, si es comprimible en el mundo, entonces.
De manera similar, también podemos construir un subconjunto, en el que todos los elementos se pueden construir usando la función y. Recordamos que es un conjunto de datos generado por funciones, por lo que obviamente existe uno. Entonces podemos definir otra función:
Entonces esta función incorpora la parte incompresible del conjunto de datos, si.
Estas dos funciones pueden describir muchas características de la suma hasta cierto punto.
Pero cómo corresponde esta propiedad a las máquinas de Turing parece un poco confuso: si reemplazamos el conjunto de funciones aquí con todas las máquinas de Turing posibles, es obvio que podemos comprimir cualquier conjunto de números enteros para no dejar ningún resto. entonces, en el caso de una máquina de Turing, se nos pediría que sumáramos la "longitud" de la propia máquina de Turing.
Pero cuando se trata de funciones, no sabemos la “longitud” de la función. Por supuesto, podríamos codificar la función como se mencionó en la sección anterior y luego usar la longitud de codificación para representar la "longitud" de la función, pero esto sería una representación impura de compresibilidad.
Lara escribió muchas ideas al observar la correspondencia entre el conjunto de Diofanto y el conjunto contable recursivo, que eran básicamente solo ideas.
Esta área parece muy interesante, pero es una pena que no haya tenido tiempo de examinarla sistemáticamente.
Este artículo cumple con la licencia CC BY-NC-SA 4.0 para el disfrute creativo.