¿Existe alguna conexión entre el problema de detención y la entropía termodinámica?

Alan Turing propuso un modelo para una máquina (Turing Machine, TM) que computa (números, funciones, etc.) y demostró el Teorema de detención .

Un TM es un concepto abstracto de una máquina (o motor si lo desea). El teorema de detención es un resultado imposible. Un Carnot Engine (CE) es un concepto abstracto de un motor térmico y Carnot demostró el Teorema de Carnot , otro resultado de imposibilidad relacionado con la entropía termodinámica.

Dado que un TM es físicamente realizable (al menos tanto como un CE, ¿o tal vez no?) ¿Existe un mapeo o representación o "isomorfismo" de TM o CE que podría permitir unificar estos resultados y además conectarse a la entropía?

Por supuesto, existen formulaciones de TM y el Teorema de detención en términos de teoría de información algorítmica (por ejemplo, Chaitin, Kolmogorov, etc.) y entropía (en ese contexto). La pregunta pide el concepto más físico de entropía (si en el proceso de una respuesta potencial surge la entropía algorítmica, está bien, pero no es lo que la pregunta pregunta exactamente).

También se puede consultar otra pregunta en física.se que relaciona la incertidumbre cuántica con la segunda ley de la termodinámica. Ver también: una caracterización algebraica de la entropía , una caracterización algorítmica de la entropía , una revisión y conexiones entre varias formulaciones de entropía

No soy en absoluto un experto en esta área, pero creo que va a estar interesado en la computación reversible . Esto implica, entre otras cosas, el estudio de la relación entre procesos que son físicamente reversibles y procesos que son lógicamente reversibles. Creo que sería justo decir que los "fundadores" del campo fueron / son Ralph Landauer y Charles H Bennett (creo que ambos investigadores de IBM).

Toca la computación cuántica y la teoría de la información cuántica, pero también examina preguntas como "¿cuáles son los límites de la computación en términos de tiempo, espacio y energía?" Se sabe (si no recuerdo mal) que puede hacer que la energía requerida para realizar un cálculo reversible sea arbitrariamente pequeña haciendo que tome un tiempo arbitrariamente largo. Es decir, la energía tiempo (= acción ) requerida para realizar un cálculo reversible se puede convertir en una constante. Este no es el caso de los cálculos no reversibles.$\times$

Muchas de las personas que estudian en esta área también están trabajando en computación cuántica y física digital (la idea de que el universo es un gran autómata celular cuántico). Los nombres de los investigadores que me vienen a la mente son Ed Fredkin , Tommaso Toffoli y Norm Margolus .

Estas preguntas son absolutamente sobre el tema de la informática. No solo para la teoría (que incluye matemática y física), sino también para los ingenieros que desean conocer los límites finales de la computación. ¿Se requiere un volumen mínimo o energía para almacenar un poco de información? La acción requerida para realizar un cálculo reversible puede ser constante, pero ¿hay límites en lo que es esa constante? Estos son conocimientos críticos para los ingenieros que intentan superar los límites de lo que es posible.

No estoy familiarizado con el Teorema de Carnot, excepto lo que acabo de leer en Wikipedia, pero incluso desde esa introducción superficial, hay una conexión en la estructura de las pruebas, y eso puede ser interesante para usted, ya que es una técnica de prueba eso es aplicable en muchos dominios.

Ambas son pruebas por contradicción para demostrar que nada en una clase dada tiene alguna propiedad, supones que alguna instancia realmente tiene esa propiedad, y luego demuestras que sigue una contradicción.

El problema de detención es interesante porque la contradicción surge de cierta interacción propia con respecto a la instancia particular (que es una máquina M que puede determinar si una máquina arbitraria se detendrá con una entrada dada). En particular, construye una nueva máquina que incluye M como componente y luego alimenta la nueva máquina a M.

Alguien con más conocimiento sobre el Teorema de Carnot podría explicarlo (para lo cual no estoy calificado), pero parece que la contradicción surge del tipo de motor térmico que podría construir si tuviera una instancia con la propiedad en cuestión.

Entonces, ambos casos involucran la construcción de:

• Supongamos que alguna X tiene la propiedad P.
  • Desde X, compila Y relacionado.
  • Las relaciones entre X e Y son contradictorias.
• Por lo tanto, ninguna X tiene la propiedad P.

Sin embargo, parece haber una diferencia, ya que la contradicción en el caso del Teorema de detención es una contradicción lógica pura y sería contradictoria en cualquier contexto de lógica clásica. El teorema de Carnot, según tengo entendido, solo es contradictorio con respecto a la segunda ley de la termodinámica. Desde una perspectiva lógica, ese es un axioma, por lo que si tomas una axiomatización diferente en la que no se cumple la segunda ley de la termodinámica, el teorema de Carnot no sería un teorema, porque la contradicción no existiría. (Lo que sería una formalización de la termodinámica sin la segunda ley es el tipo de pregunta que llevó a los geómetras a la geometría no euclidiana).

IANAPhysicist pero no veo ninguna conexión. Las máquinas de Turing son objetos de matemática pura y la indecidibilidad del problema de detención es independiente de cualquier realización física de cualquier cosa.

Esta diversa pregunta de múltiples temas no tiene una respuesta simple / fácil y toca áreas activas de la investigación de TCS. Sin embargo, es una pregunta rara sobre un vínculo entre física y TCS que me ha interesado a lo largo de los años. Hay algunas direcciones diferentes para seguir en esto. La respuesta básica es que es una "pregunta abierta", pero con algunas investigaciones activas / modernas que la abordan e insinúan conexiones.

• Hay algunos problemas sorprendentes / profundos indecidibles de la física avanzada. por ejemplo de sistemas dinámicos. sin embargo, no he visto esto conectado a la entropía per se, pero la entropía está asociada con todos los sistemas físicos (por ejemplo, uno puede ver esto en la teoría química), por lo que debe haber al menos un enlace indirecto.

• la entropía de hecho aparece en CS pero más en forma de teoría de la información y teoría de codificación. El nacimiento de la teoría de la codificación implicó la definición / análisis de entropía asociada con los códigos de comunicación de Shannon. prueba esta gran referencia en línea Teoría de la entropía e información de Gray

• la entropía también se asocia a veces con la medición de la aleatoriedad en PRNG. existe una conexión de separaciones de clase de complejidad (p. ej., P =? NP) a PRNG en el famoso documento "Natural Proofs" de Razborov / Rudich. Hay una investigación continua sobre este tema.

• Usted menciona la termodinámica y su conexión con TCS. Existe una profunda conexión entre la magnetización en los vidrios giratorios en física y los problemas completos de NP estudiados en el punto de transición SAT. allí (nuevamente) el sistema físico tiene una entropía asociada, pero probablemente se ha estudiado más en un contexto de física que en un contexto de TCS.

Hay un problema de pensamiento simple que a veces se usa como una introducción a los paradigmas informáticos no convencionales:

Tiene dos bombillas y sus respectivos interruptores de encendido y apagado. Alguien abre y cierra ambas luces una tras otra. ¿Cómo se determina cuál se cerró primero y cuál se cerró al final? Determine la cantidad mínima de veces que necesitará abrir las luces para decidir este problema.

La mayoría de los informáticos generalmente intentan encontrar alguna solución booleana basada en la lógica. La respuesta es (al menos una de ellas): tocando las bombillas y viendo cuál está más caliente.

Los paradigmas basados ​​en el calor existen en la informática: el recocido simulado es un algoritmo conocido (la computadora cuántica de ondas D es la contraparte cuántica del algoritmo).

¿Ahora hay una relación con el problema de detención?

El trabajo clásico de Chaitin y Calude sobre el problema de detención a través del concepto de números Omega se puede vincular a la formulación probabilística del problema de detención. Es el tratado más reciente sobre el problema en el que puedo pensar ... y no hay una relación clara con la entropía (termodinámica). Ahora, si la entropía de la información (en el sentido de Shannon) es buena para usted, el número Omega codifica de la manera más sucinta el problema de Detención, en el sentido de un límite de Shannon.

En resumen, un número Omega es la probabilidad de que un programa aleatorio se detenga. Conocer la constante permitiría la enumeración de todas las declaraciones matemáticas válidas (verdades, axiomas, etc.) y es indiscutible. Calude calculó una versión de Omega cambiando la medida de probabilidad uniforme con una medida inversamente proporcional a la longitud de un programa aleatorio y utilizando codificaciones sin prefijo, por lo que podríamos hablar de Omega de Chaitin y Omega de Calude.

¡Sí !, curiosamente he pensado en esto ... Aquí está la idea:

Primer paso

Modele el demonio de Maxwell como un programa de computadora. Entonces, ¿cómo Demon llegó a conocer la velocidad y la posición de las partículas antes de abrir la puerta para la selección?

Supongamos que el demonio no puede medir la velocidad a la que las partículas golpean la puerta, ¿por qué? porque eso cambiaría la velocidad de las partículas, por lo que el demonio tiene que descubrirlo antes de abrirlo, sin mirar, sin medir. Para ser justos, le haremos saber al demonio las reglas del juego de antemano, es decir, alimentar al demonio con leyes de movimiento, interacciones de partículas y condiciones iniciales, suficiente del modelo físico / dinámico.

Segundo paso

Ahora modele el gas de partículas también como un programa de computadora que ejecuta el mismo código dado al demonio para cada partícula, por lo que el gas está calculando un resultado de sus condiciones iniciales, el Demon no sabe ese resultado hasta que se detenga (si alguna vez ): a saber, "una partícula con la velocidad correcta está en la puerta", la decisión de sí / no que le hacemos al sistema es "¿Tiene una partícula la posición correcta y la velocidad suficiente?", de ser así, la puerta podría abrirse y la partícula rápida puede entrar en el lado de alta temperatura de la habitación estableciendo nuevas condiciones iniciales (¿esos problemas consecutivos tienen una respuesta o se ejecutarán para siempre?)

Habrá un momento en que no haya partículas con la velocidad suficiente para cruzar el límite, por lo que habrá un momento en que el código se ejecutará para siempre (no se detenga) en casi cualquier umbral dado.

Demon quiere saber el resultado que calcula el gas, pero el resultado está potencialmente involucrado en el código fuente de las leyes de la partícula más las condiciones iniciales ... por supuesto, necesitamos ejecutar ese programa para saberlo. Si Demon ejecuta el mismo programa esperando la velocidad correcta en la salida, el programa podría detenerse o podría ejecutarse para siempre (pero suponemos que ese demonio no tiene más poder computacional que el gas, por lo que no podrá decidir el puerta abierta a tiempo).

Daemon podría intentar averiguar la salida del programa (o si se detendrá) observando la fuente y las entradas sin ejecutarlo, pero es como tratar de resolver el problema de detención, ¿por qué? porque Demon no sabe qué leyes y condición inicial se alimentarán, por lo que debe estar preparado para resolver cualquier conjunto de leyes y condiciones iniciales, y sabemos que no es posible en general, necesitará un oráculo, si pudiera bastará para construir un demonio para generar energía de la nada (incluso conociendo las leyes y la condición inicial, ambas cosas ya son lo suficientemente difíciles de saber)

Este experimento mental puede vincular cómo una reducción en la entropía, por medio de las computadoras, podría de alguna manera estar limitada por Halting Problem , como un problema para anticipar en general los resultados.

(En algún momento todos los límites parecen ser el mismo límite ..)

Más acerca de las leyes de partículas

Las leyes de partículas no son el tema principal de este experimento mental, esas leyes podrían ser cuánticas o clásicas, pero debemos tener en cuenta el hecho de la complejidad de las leyes y las condiciones iniciales, la complejidad de la disposición de las partículas no está limitada, y podría tienen mucha complejidad adicional (en un ejemplo extremo de condiciones iniciales, incluso podría insertar una computadora completa disparando partículas de acuerdo con un código fuente interno y darle ese código al demonio).

Pregunta realmente cautivadora, y veremos que su pensamiento ES correcto .

Primero veamos qué dice el segundo principio de la termodinámica.

La función de entropía se usa en la segunda ley de la termodinámica. Se deriva del teorema de Carnot que establece que los procesos que tienen lugar en máquinas de vapor tienen una eficiencia menor o, en el mejor de los casos, igual a la máquina "reversible" correspondiente (que por cierto parece un concepto inestable durante los 150 años de termodinámica). Carnot no acuñó la función de entropía, pero junto con Clausius esto es lo que dicen:

Como no hay una máquina perpetua, entonces podemos construir una función S llamada entropía que restringe las medidas termodinámicas macroscópicas en una determinada ecuación, a saber, S (V, T, P, etc.) = 0

Tenga en cuenta que esta ecuación no es más que la ecuación de una hiper-superficie en el espacio de medidas termodinámicas.

Entra en Carathéodory.

Carathéodory es un matemático alemán y, como todos los matemáticos, quiere extraer de Carnot y Clausius razonando algunos axiomas que le permitirían aclarar de qué se trata realmente la segunda ley . Dicho sin rodeos, quiere purificar la termodinámica para saber exactamente qué es la entropía.

Después de enumerar una cierta cantidad de axiomas, logra formular SU segunda ley, que dice (más o menos):

Hay algunos procesos adiabáticos. O más prosaicamente, si quieres regresar, a veces trabajar solo no es suficiente. Necesitas un poco de calor.

¡Ahora eso parece MUY diferente de la formulación de Clausius! Pero de hecho no lo es. Todo lo que Carathéodory hizo fue cambiar el orden de las palabras, un poco como los matemáticos jugaron con el quinto axioma de Euclide durante 2.000 años y produjeron muchas palabras diferentes para ese axioma. Y si retrocede, no debería sorprenderse demasiado con la declaración de Carathéodory de la segunda ley. De hecho, Carathéodory conduce a la misma función de entropía y ecuación de hiper-superficie S (V, T, P, etc.) = 0

Piensa bien en el teorema de Carnot. Como matemático, no debe estar demasiado satisfecho de la forma en que Carnot admite que las máquinas perpetuas no existen. De hecho, como matemático, preferiría ver algo como esto:

Hay una función de entropía S que restringe las medidas macroscópicas SI Y SOLO SI no hay máquinas perpetuas ".

AHORA tienes un teorema. Y que dice Que mientras no exista un sistema mecánico aislado que produzca una cantidad infinita de energía y, por lo tanto, pueda llevarlo al estado que desee, encontrará una función de entropía. Un sistema mecánico aislado es un proceso adiabático. De ahí la formulación de Carathéodory: ningún sistema adiabático puede llevarlo a ninguna parte. A veces necesitarás algo de calor.

Entonces, no solo estamos seguros de que Carathéodory es correcto, sino también de que su formulación es bastante simple.

Ahora, ¿dónde tiene la impresión de que la segunda ley a la Carathéodory es similar al problema de detención?

Da un paso atrás en la declaración de Carathéodory. Todo lo que dice es que una vez que tiene un sistema mecánico aislado con el que deja de mezclarse, no puede alcanzar el estado que desea.

¿No suena PRECISAMENTE como el problema de detención? Es decir, una vez que haya escrito todos los axiomas de su teoría y haya establecido todas las transiciones posibles, habrá problemas que no podrá resolver. A veces, necesitará agregar más axiomas.

De hecho, si desea profundizar y codificar la formulación de Carathéodory, esto dará como resultado el mismo código que el problema de detención con procesos adiabáticos en lugar de máquinas Turing, y estados en lugar de problemas.

¿Qué piensas?

NOTA: edité mi respuesta casi por completo para que los comentarios a continuación no coincidan con lo que contiene ahora.