¿La existencia de problemas indecidibles implica inmediatamente la no previsibilidad de los sistemas físicos? Consideremos el problema de detención, primero construimos un UTM físico, digamos usando la construcción basada en circuito habitual. Entonces no puede haber una teoría física decidible que pueda determinar, dada la configuración de entrada de los circuitos, si el circuito se detendrá. Esto parece una trivialidad, pero ¿no nos da un tipo de imprevisibilidad débil sin referencia a consideraciones cuánticas o caóticas? Además, podemos fortalecer el argumento anterior al señalar que no hay nada especial sobre el UTM basado en circuito, por lo que tenemos que el comportamiento de un sistema físico es en general indecidible en cualquier nivel donde se pueda construir un UTM.
Editar: como señalaron tanto Babou como Ben Crowell, mi construcción de circuito sugerida es simplemente un LBA. Como dije en los comentarios, me resulta fácil e intuitivo imaginar una máquina que sea física pero que no esté linealmente acotada. Simplemente construya una máquina (robot) que pueda moverse mecánicamente de izquierda a derecha en una entrada arbitrariamente muchas veces, y suponga que tiene una fuente de energía finita, pero que no caduca. Ahora también nos encontramos con el problema de que el universo es finito, pero eso nos permite concluir que el universo es finito o que la consecuencia originalmente esperada debe ser cierta (que aún sería una conclusión sorprendente a partir del argumento anterior) .
fuente
Respuestas:
Inicialmente, esto fue pensado como un comentario, ya que evita un poco la pregunta. Pero creo que responde a su manera.
Lo que se sabe, o se intenta hasta ahora, muestra que conectar la teoría de la computación con la física puede ser un esfuerzo bastante sutil, y me temo que el enfoque sugerido en la pregunta es probablemente demasiado crudo. No estoy seguro de que sea mucho mejor que el argumento clásico de que, siendo todo finito, todo lo que necesitamos es la teoría de autómatas de estado finito, y que estudiar las máquinas de Turing es una pérdida de tiempo. (No es mi punto de vista de las cosas)
¿Por qué deberían abordarse estos problemas con precaución?
Probablemente debería motivar la comparación anterior con el argumento de autómatas finitos. Mi percepción es que la computabilidad es, quizás incluso más que la complejidad, una teoría asintótica: lo que importa es lo que ocurre en el infinito. Pero no sabemos si el universo es finito o infinito. Si es finito, ¿cuál sería el punto de considerar cálculos infinitos? Lo siguiente se refiere a la física, y yo no soy físico. Hago mi mejor esfuerzo para ser exactos, pero te han advertido .
A menudo vemos el Big Bang como un "tiempo" cuando todo el universo era algo muy pequeño, con un tamaño muy pequeño. Pero si tenía un tamaño en algún momento, ¿cómo se transformó en algo infinito en un momento posterior? No estoy tratando de decir que es imposible ... No tengo la menor idea. Pero podría ser que siempre fue infinito.
Entonces, consideremos el universo como infinito. Nos ayuda? Bueno, tenemos algunos problemas con la velocidad de la luz. Si consideramos lo que puede ser relevante aquí (dónde estamos), tenemos que considerar que solo podemos preocuparnos por una parte del universo que está incluida en una esfera finita. El radio de esa esfera es tal que la velocidad relativa de dos puntos a la distanciarr r debido a la expansión es igual a la velocidad de la luz. Según lo que sabemos actualmente, sin una variación futura en la velocidad de expansión, nada fuera de esa esfera nos preocupará. Entonces, el universo es finito para nosotros a todos los efectos prácticos. En realidad, las cosas son aún peores si se considera el contenido de este universo relevante: se está reduciendo (a menos que haya algún proceso de creación). La razón es que la esfera se está expandiendo más allá de su propio diámetro, llevando consigo parte de su contenido que también se vuelve irrelevante. Observación: esa esfera no es lo que se llama el universo observable (que depende de la edad del universo), es mucho más grande.
Por lo tanto, no solo "nuestro" universo es finito, sino que sus recursos podrían estar disminuyendo. Es posible que en tantos miles de millones de años, solo nuestra galaxia siga siendo relevante para nosotros (suponiendo que sigamos existiendo), con la galaxia de Andrómeda que llegará a la Vía Láctea antes de eso.
Bueno, no sé qué se considera establecido en este momento, pero muestra al menos que asumir el infinito es una gran suposición.
Sin embargo, es el caso que las limitaciones físicas nos impiden usar la teoría de la computabilidad. Todo lo que se puede concluir de lo anterior es que puede ser irrazonable sacar conclusiones físicas del trabajo teórico sobre las máquinas de Turing y el problema de la detención.
Sin embargo, las técnicas en cuestión también pueden dar resultados útiles cuando se aplican a dispositivos o formalismos que no son completos de Turing. No trataría de entrar en detalles, aunque solo sea porque la complejidad algorítmica no es mi área, pero supongo que, si la estructura del universo es discreta, la complejidad podría ser de alguna forma relevante para el comportamiento de algunos fenómenos. Por supuesto, esto es solo una especulación salvaje de mi parte. Algunas de las investigaciones a las que me refiero a continuación están relacionadas con tales problemas de discreción.
Algunos ejemplos de trabajos relacionados con la física y la teoría de la computación.
Hay una gran cantidad de trabajo tratando de vincular la computación y la física, la mayoría de los cuales apenas sé. Entonces, por favor, no confíe en nada de lo que pueda decir , sino simplemente tómelo como punteros para buscar trabajo potencialmente relevante.
Una buena parte de ese trabajo se refiere a aspectos termodinámicos, como la posibilidad de computación reversible sin costo de energía. Creo que esto se relaciona con la programación funcional, ya que son los efectos secundarios los que cuestan energía (pero no confían en mí). Puede tomar wikipedia como introducción, pero Google le dará muchas referencias .
También hay trabajo tratando de vincular la tesis y la física de Church-Turing, involucrando la densidad de información entre otras cosas. Ver por ejemplo:
La tesis física de Church-Turing y los principios de la teoría cuántica.
En torno a la tesis física de Turing de la Iglesia: autómatas celulares, lenguajes formales y los principios de la teoría cuántica ,
Tesis de Física y Turing de la Iglesia .
Recuerdo vagamente haber visto otras tomas interesantes sobre esto, pero se me escapa en este momento.
Luego tiene el trabajo de Lamport en la sincronización de relojes y la relatividad en sistemas distribuidos .
Y, por supuesto, tiene computación cuántica que aparentemente cambia algunas complejidades de tiempo (alcanzables), aunque no afecta la computabilidad.
Otra toma es el trabajo de Wolfram en el modelado de leyes físicas con autómatas celulares , aunque los beneficios reales de este trabajo parecen discutidos.
Creo que tratar de comprender todo este trabajo podría acercarlo a comprender cómo puede vincular algunos conocimientos de computabilidad con (como implicando) limitaciones teóricas del mundo físico, aunque la tendencia hasta ahora era más vincular las limitaciones de computabilidad (como consecuencias de) propiedades del universo físico.
Un posible problema en todo esto es la autoinserción de todas nuestras teorías (matemáticas, computación, física, ...) dentro de los límites de los conceptos que son sintácticamente expresables (es decir, por un lenguaje) que pueden establecer un límite en el poder expresivo de nuestra ciencia Pero no estoy seguro de si la oración anterior tiene significado ... perdón por eso, es lo mejor que puedo hacer para expresar una duda persistente.
Como explicación de la decepción personal , agregaría que los físicos (al menos en http://physics.stackexchange.com ) no son muy amigables para discutir lo que otras ciencias podrían decir sobre cuestiones físicas (aunque están bastante dispuestos a discutir qué puede decir la física sobre otras ciencias).
fuente
La pregunta se refiere en parte a la imprevisibilidad de los sistemas físicos . La indecidibilidad aparece en algunos problemas de física. Una encuesta temprana realizada por esto es de Wolfram, Indecidibilidad e Intractabilidad en Física Teórica (o aquí ) y esta área continúa expandiéndose. Sin embargo, una mejor manera de comprender la imprevisibilidad física inherente es más a través de lo que se conoce como "dependencia sensible de las condiciones iniciales", también conocido como efecto mariposa . Esto se puede estudiar utilizando el atractor de Lorentz como modelo de semi-juguete.
fuente
La pregunta es interesante (es posible que desee verificar una pregunta relacionada "¿Existe una conexión entre el problema de detención y la entropía termodinámica?" )
El núcleo del problema es ¿qué viene primero de las matemáticas o la física? Bueno, la física es la respuesta . Una cita de Einstein dice: " el tipo de matemática que hacemos depende del mundo en que vivimos " (si no me equivoco, esto está en "Einstein, filósofo-científico") (y otro relacionado y ligeramente parafraseado) "La naturaleza sí no nos importan nuestras dificultades matemáticas. Se integra empíricamente " ). Entonces, en este sentido, ciertas características físicas se reflejan en el simbolismo matemático y el procedimiento. Pero también se puede tomar la opinión opuesta de que las matemáticas definen la física (una opinión que es bastante popular en ciertos círculos).
Hay un pasaje en la introducción del libro "Álgebra lineal" de J B. Fraleigh, R A. Beauregard (un buen libro sobre el tema y un punto que quería abordar dada la oportunidad)
Sin embargo, esto no es cierto , de hecho hay algo que experimentamos y es uno (literalmente) , el sol (cuidado con las estrellas de la noche ni la luna que no se percibe como una en todas las circunstancias, el sol, el único y visible cosa en el cielo a la luz del día). (y de hecho ha sido históricamente un objeto de honor y asombro de la humanidad). Uno puede continuar y discutir otras cosas que experimentamos como dos o tres y cuatro ( dos manos, cinco dedos, etc.), pero se ha dado el punto principal (para obtener más información, busque " prehistoria e historia de los sistemas numéricos"). ")
Digamos por un minuto que un resultado matemático indicaría algo, pero luego una teoría física proporcionaría un procedimiento para lograr lo contrario (efectivamente, una prueba constructiva de lo contrario). Entonces algo estaría mal, estos están relacionados especialmente cuando usan exactamente el mismo formalismo. Es intuitivo que estos deberían estar relacionados de alguna manera.
Por ejemplo, un resultado de imposibilidad matemática limitaría la descripción matemática de una teoría física que necesitaría tal resultado, etc. Un ejemplo que puedo usar en este momento es la llamada "teoría de todo". Se supone que describe en forma matemática todas las interacciones físicas que tienen lugar, por lo que, de hecho, describe todo. Sin embargo, según el teorema de Goedel, se sabe que dicha descripción sería incompleta en un sentido u otro. ¿Esto dice algo sobre el mundo en que vivimos? Más probablemente.
Pero los resultados de imposibilidad se conocen en términos puramente físicos y la mayoría de ellos están relacionados con la termodinámica. Por ejemplo "El calor fluye de caliente a frío". Este es un resultado imposible. Pero esto también limita cualquier resultado matemático que implicaría (cuando se aplica en el contexto apropiado) que el calor fluye de frío a calor , esto no sucede. Entonces las matemáticas pueden estar limitadas por términos físicos . La verdadera pregunta es cuál es la conexión exacta (si la hay) entre estos dos y esta es una pregunta muy interesante con resultados interesantes y de largo alcance. Por ejemplo, puede verificar el trabajo de G. Chaitin que relaciona la teoría de la información, los teoremas de Goedel y los sistemas biofísicos.para comenzar. Algunas otras conexiones ya se han mencionado como la computación reversible, la computación cuántica, etc.
Por último, pero no menos importante, recuerda que la física depende del experimento para formular y verificar cosas y no pruebas simbólicas . (A) La descripción matemática de una teoría física es importante en términos de cálculos, por lo que una matemática problemática puede limitar o plantear problemas en el poder de cálculo de la teoría, sin embargo, el experimento permanece. Y recuerde que los físicos suelen estar entre los creadores de nuevas matemáticas, según sea necesario (por ejemplo, cálculo y ecuaciones diferenciales, probabilidades, análisis de tensor, procedimiento de renormalización en mecánica cuántica, regularización analítica, etc.)
Con respecto a su ejemplo que conecta la imposibilidad de predecir con un TM, la conexión se puede hacer y puede requerir una cinta sin límites, siempre que la máquina necesite calcular con precisión infinita (es decir, números irracionales / trascendentales que de ninguna manera están excluidos de un físico). sistema). Entonces, una máquina LBA no será lo suficientemente potente como para calcular un sistema físico dado y uno ingresa a la cinta UTM infinita que tiene un problema de detención. La cuestión de si la imprevisibilidad se puede atribuir a las condiciones iniciales (la definición formal enseñada del comportamiento caótico) o el cálculo en sí mismo no es esencial, ya que solo cambia el problema a otro lugar en lugar de abordarlo.
fuente
Babou
De hecho, es una pregunta muy interesante, pero como se dijo anteriormente, se ha producido mucha literatura sobre el tema. Lo menos que puede decir una vez que haya leído todo eso es que el mapeo de UTM a sistemas físicos está lejos de ser sencillo, por seductora que sea la idea.
Personalmente, me gusta comenzar desde el concepto de computación reversible introducido por Landauer y mencionado en las respuestas anteriores. Parece haber una conexión conceptual entre entropía y UTM.
Piénselo de esta manera: imagine que quiere caminar desde el punto A al punto B (geográficamente distinto) usando un plan determinista (es decir, una serie de pasos que se pueden escribir de antemano como un UTM: camine recto durante 100 m, gire a la derecha en La panadería, caminar 50m etc.). Puedes caminar la distancia una vez. Dos veces. Tres veces. ¿Cuántas veces puedes hacerlo? A menos que incluya un stock infinito de alimentos y agua en su plan, tendrá que detenerse después de un número finito de viajes. Pero aunque una cinta UTM es infinita, el número de pasos de la propia TM debe escribirse en un número finito de caracteres. Por lo tanto, su plan no puede incluir una cantidad infinita de alimentos y agua.
Ahora la energía es una cantidad conservadora. Entonces podría pensar que una cantidad finita de provisiones debería ser suficiente. Pero claramente este no es tu problema aquí. Incluso si viaja muy lentamente entre A y B, su cuerpo convertirá su comida en algo que ya no podrá consumir. Tenga en cuenta que si intenta escapar de ese problema e ir INFINITAMENTE lento (casi estáticamente entre A y B), ya no podrá escribir su "plan" con un número finito de caracteres. Por lo tanto, es el aumento de la entropía termodinámica (degradación de los alimentos y el agua a través del procesamiento de su cuerpo) lo que parece representar un límite para la cantidad de viajes que puede realizar mientras se apega a un plan determinista (es decir, un UTM).
Si esto es correcto, la imprevisibilidad de TM debe asignarse al aumento de la entropía termodinámica.Tenga en cuenta que esto parece bastante contra-intuitivo (como se dijo antes, ese tipo de mapeo está lejos de ser trivial): al infinito, el aumento de la entropía termodinámica conduce a un equilibrio, es decir, algo estable; pero el mismo límite infinito del UTM correspondiente conduce a un comportamiento aleatorio (es decir, no estamos seguros de qué tipo de salida). Eso es aún más sorprendente con una pelota rodando por una curva convexa con fricciones: la entropía termodinámica hace que la pelota se detenga en el bajo reflujo de la curva, lo cual es algo bastante fácil de predecir; pero el UTM equivalente le dirá que "algo al azar" sucede al final que no se puede predecir. ¿Es que tenemos que mapear esa imprevisibilidad al movimiento aleatorio de los átomos creado por la disipación de calor del movimiento de la pelota contra la superficie de la curva? Ese'
¡Espero que ayude!
fuente
Creo que un buen modelo para esto es el juego de la vida de Conway.
Desde que inventamos las reglas, las conocemos perfectamente. Esto es análogo a una teoría física.
Sin embargo, a pesar de lo simples que son las reglas y el hecho de que las conozcamos, la vida es indecidible .
Del mismo modo, incluso si aprendiéramos todas las leyes de la física, podría resultar que también son indecidibles.
Realmente no hay nada que puedas hacer al respecto. Sin embargo, una cosa a tener en cuenta es que puedes predecir el juego de la vida de Conway para cualquier número finito de pasos . Esto podría ser lo mismo para la física.
fuente
No.
Una máquina universal de Turing es una máquina de Turing. Una máquina Turing tiene una cinta infinita (o infinitamente extensible). Por lo tanto, no puedes construir uno fuera de los circuitos. Lo que puede construir es un autómata lineal acotado (LBA).
El problema de detención es decidible para un LBA, por lo que su argumento falla.
fuente