¿Existen proposiciones indecidibles en la mecánica clásica?

¿ Los teoremas de incompletitud de Gödel tienen algún significado o aplicación para las teorías axiomáticas de la mecánica clásica como la de Newton, por ejemplo?

No lo sé, pero las únicas "declaraciones indecidibles" de las que he oído hablar eran autorreferenciales. Es decir, un enunciado expresado en el lenguaje de algún sistema formal, que describe un enunciado expresado en el mismo sistema formal, que resulta ser él mismo. El objetivo de la mecánica clásica es describir el mundo físico. ¿Tendría incluso sentido hablar de un enunciado de la mecánica clásica que describe un enunciado de la mecánica clásica en lugar de describir algún sistema físico?
@SolomonSlow: el truco es codificar la declaración de mecánica clásica más la mecánica clásica en un sistema formal que luego se implementa utilizando un sistema de mecánica clásica. Una situación muy artificiosa, seguramente, pero totalmente permitida.
Relacionado: physics.stackexchange.com/q/14939/2451 y enlaces allí.
Dejar pag denota un teorema físico, y q una declaración matemática que sigue siendo indecidible incluso dada toda la física. Entonces pag q calificaría, pero probablemente quiera un ejemplo más interesante. Entonces, ¿cuáles son las reglas aquí?
Esa es una gran pregunta, pero lástima que tuvo una mala respuesta.

Respuestas (4)

Sí. Una forma simple (trivial) de verlo es considerar una computadora mecánica y preguntar si uno puede predecir su estado final dado el estado inicial sin ejecutarlo. Dado que este es exactamente el problema de detención de Turing, cualquier método que le permita hacer esa predicción en la mecánica newtoniana sería un contraejemplo del teorema (contradicción) o requeriría algún elemento no computable.

Esto no debería ser sorprendente. Los sistemas dinámicos caóticos carecen de soluciones analíticas ya menudo son indecidibles . Esto parece ser cierto (uno necesita definir decidir cuidadosamente aquí) para el problema de N-cuerpos (ver también esta disertación ).

¿Importa esto? Probablemente menos a los físicos y más a los filósofos e informáticos. La cuestión de cómo se incorpora la computación en el mundo físico es un gran tema, con preguntas interesantes sobre si la hipercomputación es posible de verdad (está permitida en la mecánica newtoniana; en principio, se puede resolver el problema de la detención usando una configuración newtoniana ) y si la física Las leyes son de pronóstico.

No estoy seguro de si la "indecidibilidad" en Gödel y en Turing significa lo mismo.
El problema de la detención de Turing simplemente dice que no puedes hacer una máquina de Turing que pueda decirte, para todas las máquinas de Turing, si se detienen. No dice que, para una máquina de Turing en particular , no podemos decir si se detiene.
Sí, por lo tanto, no hay una máquina de Turing que pueda calcular el resultado de todas las máquinas mecánicas [o decirlo, si no hay resultado, porque la máquina mecánica nunca se detiene]. Pero, ¿significa que el NM es indecidible? En la lógica matemática, un enunciado es indecidible, si no se puede demostrar y no se puede refutar en el sistema de axiomas en el que se formula. Si es equivalente a que ninguna TM pueda resolverlo en el caso general, eso para mí no es trivial.
@peterh-ReinstateMonica Creo que la correspondencia Curry-Howard implica que son lo mismo. Dada una proposición matemática, construya una máquina de Turing que emita 1 si es un teorema y 0 si no es un teorema. Si es indecidible, entonces no puede generar nada y, por lo tanto, no debe detenerse. No es riguroso, pero creo que esa es la esencia. en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondencia
No puedo estar de acuerdo con esta respuesta ya que el problema de la detención está íntimamente ligado a la naturaleza ilimitada de las máquinas de Turing, mientras que cualquier computadora física tendría que estar limitada y, por lo tanto, ser computacionalmente equivalente a un autómata finito, para el cual se puede determinar la detención.
@kviiri Creo que la "computadora física" idealista, en el marco de esta publicación, debe ser finita, pero puede ser grande. ("¿finito pero ilimitado"? No estoy seguro de que esta sea la terminología correcta)
@kviiri ¿Por qué tendría que estar limitada una computadora física?
@peterh-ReinstateMonica Cualquier computadora finita, sin importar cuán grande sea, es "inmune" al problema de la detención, por así decirlo, porque tendrá una cantidad finita de estados y, por lo tanto, se detendrá o visitará uno de estos estados más de una vez. , sin detenerse nunca.
Es un buen intento, pero estoy de acuerdo con @kviiri. Cualquier computadora física debe estar hecha de norte partículas con norte < 10 200 decir. El problema de Halting para cualquier computadora de este tipo es decidible.
@JiK No estoy lo suficientemente versado en mecánica clásica para decir si sus formulaciones habituales permiten objetos de tamaño infinito, lo que sería necesario para una máquina de Turing verdaderamente general. Sin embargo, en caso de que Anders quiera argumentar basándose en eso, al menos deberían señalar que están hablando explícitamente de una computadora mecánica muy especial con propiedades muy inusuales.
Tenga en cuenta que la pregunta era sobre la mecánica newtoniana, no sobre la física estándar. En el formalismo definitivamente se permiten números infinitos de partículas y momentos arbitrariamente altos.
Por otro lado, la hipercomputación está integrada en GR.
@lcv Cualquier prueba que resuelva la decidibilidad para ese cálculo físico específico puede tomar más de 10 200 partículas para escribirlo...
Espera, entonces, ¿las preguntas básicamente indecidibles siempre son solo sobre infinitos?
@Ezio: una pregunta indecidible no se puede responder utilizando medios computacionales finitos. Tenga en cuenta que no tiene que tratarse de un sistema infinito: uno puede establecer un sistema de N-cuerpos para algún N finito y preguntarse si siempre permanecerá acotado o si las partículas finalmente saldrán disparadas, y esa pregunta puede ser indecidible.
Entonces, sí, es suficiente para mostrar la indecidibilidad de Turing, ya que está trabajando en un sistema con un conjunto enumerable de axiomas, por lo que si pudiera probar para cada máquina de Turing que no es la mitad que no es la mitad, habría enumerado todos los que no se detienen. máquinas y (como puede enumerar fácilmente las máquinas que se detienen) tendría una solución computable para el problema de la detención (solo vea en qué enumeración aparece su máquina).
Sin embargo, creo que una prueba completa de esto requeriría elegir una axiomitazación y un idioma en particular para trabajar y verificar que realmente puede escribir una fórmula finita en ese idioma que corresponde a la parada de la máquina de Turing. Por ejemplo, ¿es posible modelar exactamente una máquina de Turing en mecánica clásica? Debe verificar que no se trata solo de que pueda encontrar una configuración que calcule los primeros 10 ^ 20 pasos correctamente, sino todos. Me preocuparía que solo pudieras representar mejores y mejores aproximaciones de la máquina T. Probablemente no, pero habría que comprobarlo.

El teorema tiene consecuencias para cualquier sistema formal que incluya aritmética. Siempre habrá teoremas que serán indecidibles. Esos teoremas, sin embargo, siempre implican cantidades infinitas, un ejemplo es: ¿Este sistema de ecuaciones diofánticas tiene un número finito o infinito de soluciones?". El problema es en general indecidible, aunque para ejemplos particulares puede resultar decidible. Otros más interesantes se pueden encontrar ejemplos aquí , y también en la respuesta de @Anders Sanberg

Me gustaría compartir dos ejemplos que uno podría considerar una "versión física" del teorema de incompletitud de Gödel. Esto realmente no responderá a la pregunta de si los sistemas de axiomas en física pueden ser formalmente incompletos en el sentido de Gödel. Sin embargo, mostrará cómo la incompletitud de una teoría física suele estar conectada con alguna percepción física que no es capturada por el sistema de axiomas, y que una incompletitud matemática, por lo tanto, simplemente indicaría que nuestra teoría no describe toda la física. (Este argumento asume el determinismo, pero dado que la pregunta es sobre mecánica clásica, creo que es justo).


El primer ejemplo es la cuna de Newton , o una versión simplificada donde tres esferas idénticas perfectamente incompresibles se alinean perfectamente en el espacio y chocan a lo largo de una línea. Pictóricamente (o = esfera, o> = es esfera en movimiento, -= separación espacial):

--o>---o---o---

Desde una perspectiva axiomática, tenemos las leyes de Newton (principalmente la conservación del momento relevante aquí) y la suposición de esfera perfectamente incompresible (que da la conservación de la energía ).

Para dos bolas (--o>----o--), el problema se resuelve mediante la conservación de la cantidad de movimiento y la energía y se encuentra que la primera bola se detiene mientras que la segunda bola toma la cantidad de movimiento de la primera. No hay ningún problema aquí.

Para tres bolas (--o>----o----o---), el problema es simplemente una sucesión de colisiones de dos bolas.

El problema se vuelve interesante cuando dos de las bolas se tocan al principio (--o>---oo----). Al configurar la conservación de la cantidad de movimiento y la energía para este sistema, se encuentra que las ecuaciones tienen múltiples soluciones físicas , siendo la solución de dos colisiones sucesivas de dos bolas solo una de ellas. En cierto sentido, el problema es indecidible dentro de nuestro "sistema de axiomas".

¿Que está sucediendo aquí? La respuesta es muy simple: la suposición de la esfera perfectamente incompresible no tiene mucho sentido cuando dos bolas se tocan. En realidad, incluso si las bolas son perfectamente incompresibles en un sentido limitado, habrá ondas visibles que se desplazarán a través del material y provocarán que se realice físicamente una trayectoria única. Nuestros axiomas no capturan esta situación.


Otro conjunto de ejemplos famosos son varias paradojas en relatividad especial (por ejemplo, la paradoja de la víbora L ), que al final requieren que se abandone el concepto de un cuerpo rígido perfecto.


El ejemplo de la cuna de Newton es indecidible en un sentido físico. Sin embargo, en un sentido matemático, esto no tiene nada que ver con el teorema de incompletitud de Gödel. Las paradojas de la relatividad especial son un ejemplo de axiomas que físicamente no van juntos.

Buen ejemplo (+1). Aunque parece que todas las situaciones aparentemente indecidibles de Goedel en la física, se vuelven decidibles cuando uno inserta adecuadamente las limitaciones físicas (como, no hay cuerpo elástico perfecto, no hay rígido perfecto, ..)
No creo que "tener soluciones múltiples" sea en ningún sentido lo mismo que el problema sea indecidible. En el caso de soluciones múltiples hemos resuelto el problema , solo que su solución no es única. En el caso de la indecidibilidad, hemos demostrado que es imposible llegar a una solución general.
@ACuriousMind Depende de lo que quiera decir con "el problema". Si desea saber qué sucede físicamente , el sistema de axiomas considerado no responde la pregunta. Soy consciente de que esto no es lo mismo que la indecidibilidad en el sentido de Gödel y lo especifiqué en mi respuesta. Mi punto es que investigar los teoremas de Gödel para las teorías físicas solo es útil en un sentido limitado, ya que una incompletitud es inherentemente no física. ¿Alguna sugerencia para aclarar eso en mi respuesta?

Si estás siendo estricto con el tipo de cosas de las que hablaba Gödel, no. Godel estaba operando en sistemas que podían probar todo enunciado verdadero en aritmética. En física, estas son generalmente afirmaciones que se suponen en lugar de probarse. La física se basa en las matemáticas, basándose en lo que las matemáticas afirman que es verdad.

Para empezar, necesitarías encontrar algo cuantizado en la mecánica clásica. La mayoría de los temas de mecánica clásica tratan con números reales y, por lo tanto, las declaraciones más significativas se prueban utilizando la lógica de segundo orden (SOL). Gödel demostró que los sistemas SOL no pueden admitir una prueba de su propia consistencia, pero más allá de eso, tiene poco que decir sobre tales sistemas.

También necesitaría encontrar un sistema autorreferencial cuantizado , y luego uno que admita algo parecido a una prueba de su propia consistencia.

De hecho, la verdadera auto referencia en sí misma es bastante rara en física, y un poco novedosa. Pero es posible que pueda encontrar algo en lo que hincar el diente en el mundo de tratar de modelar cómo piensa el cerebro. Pero cuanto más aprendemos sobre el cerebro, más aprendemos cuán poco depende de algo tan frágil como la lógica.

Eso no es realmente cierto. El teorema de incompletitud se aplica a cualquier sistema formal que contenga aritmética. En última instancia, cualquiera que sea el sistema deductivo que use en física, debería poder encontrar declaraciones indecidibles.
Creo que cualquier sistema formal que contenga aritmética es autorreferencial por defecto
@Ezio Creo que la verdadera aritmética es un sistema formal que es completo y consistente. Por supuesto, no se genera de manera efectiva. Esto trae a colación una peculiaridad divertida de la pregunta. Si los sistemas que observan los físicos no se esfuerzan por cumplir con los requisitos muy específicos de los sistemas sobre los que Godel estaba haciendo pruebas, ¿eso significa que están afectados o no por sus teoremas?
No creo que sea una cuestión de creencia. No estoy seguro de cuán afectados son los sistemas axiomáticos de la física, esta es la pregunta.
@Ezio Bueno, en el corazón de la física está la cuestión filosófica fundamental de la ciencia. ¿Estamos descubriendo leyes fundamentales de la física o estamos identificando patrones que vemos dondequiera que miremos? Este último es completamente inmune al pensamiento godeliano en todos los sentidos, porque no busca probar cosas.
Mire, por mi parte, no me suscribo a las distinciones artificiales entre la física matemática y la filosofía. Comprender la filosofía natural es comprender la naturaleza de la realidad y eso es lo mismo que comprender las matemáticas. En uno de estos campos, estamos buscando patrones comunes (fundamentales) = leyes que existen de alguna forma, independientemente de las escalas o áreas particulares.
@Ezio Entonces, usando esas palabras, la física no es un campo que nos permita identificar leyes naturales, simplemente cosas que aparecen en nuestras facultades limitadas como leyes naturales y pueden probarse como tales. La mayoría de las veces, este matiz tiene una importancia limitada, pero cuando nos adentramos en límites teóricos como los que demostró Gödel. No hemos probado la existencia de todos los números enteros en el mundo real, simplemente encontramos sistemas que sugieren números tan grandes que podemos creer que se extenderán para siempre.
Las leyes naturales pueden provenir "de más allá de la física", de la filosofía o de algún elegante conjunto de reglas matemáticas que describen todas las interacciones en el mundo real concreto. Ni siquiera sé cómo se distinguiría con precisión entre el reino platónico de las matemáticas y este mundo real y cuál tiene una existencia más "real". Lo que Godel demostró esencialmente es que la demostrabilidad es limitada, lo cual es bastante obvio, ya que uno siempre tiene que suponer algo para probar algo. Así que siempre habrá algo fuera de la capacidad lógica o física para probar o medir tanto en el mundo real como en el platónico.
Hay que distinguir dos cosas. Los sistemas Godel (bueno, Godel, Rosser, etc.) demostraron contener enunciados formalmente indecidibles (aquellos que extienden ciertos sistemas débiles de aritmética) y aquellos sistemas axiomáticos cuyo problema de decisión (puede u computable decidir si phi es demostrable para cualquier phi) es decidible. Hay muchos sistemas que no amplían la aritmética que todavía no son decidibles. Todo esto sobre QM y la naturaleza de la física no es realmente relevante ya que Q solo está bien definido en relación con un conjunto específico de axiomas (la indecidibilidad puede depender de cómo represente el sistema)