Existe uma conexão entre o problema da parada e a entropia termodinâmica?

Alan Turing propôs um modelo para uma máquina (a Máquina de Turing, TM) que calcula (números, funções, etc.) e provou o Teorema da Halting .

Uma TM é um conceito abstrato de uma máquina (ou mecanismo, se você preferir). O Teorema da Parada é um resultado impossível. Um Motor de Carnot (CE) é um conceito abstrato de um motor térmico e Carnot provou o Teorema de Carnot , outro resultado de impossibilidade relacionado à entropia termodinâmica.

Dado que uma MT é fisicamente realizável (pelo menos tanto quanto uma CE, ou talvez não?), Existe um mapeamento ou representação ou "isomorfismo" de MT ou CE que permita unificar esses resultados e conectar-se à entropia?

É claro que existem formulações da MT e do Teorema da Halting em termos de teoria algorítmica da informação (por exemplo, Chaitin, Kolmogorov etc.) e entropia (nesse contexto). A pergunta pede o conceito mais físico de entropia (se no processo de uma resposta potencial surgir entropia algorítmica, está bom, mas não é exatamente o que a pergunta pergunta).

Pode-se também verificar outra questão em physics.se, que relaciona a incerteza quântica com a 2ª lei da termodinâmica. Veja também: uma caracterização algébrica da entropia , uma caracterização algorítmica da entropia , uma revisão e conexões entre várias formulações da entropia

Não sou especialista nesta área, mas acredito que você estará interessado em computação reversível . Isso envolve, entre outras coisas, o estudo da relação entre processos fisicamente reversíveis e processos logicamente reversíveis. Eu acho que seria justo dizer que os "fundadores" da área eram / são Ralph Landauer e Charles H Bennett (acho que são as duas pesquisas da IBM).

Ele aborda a computação quântica e a teoria da informação quântica, mas também examina questões como "quais são os limites da computação em termos de tempo, espaço e energia?" Sabe-se (se bem me lembro) que você pode tornar a energia necessária para executar um cálculo reversível arbitrariamente pequeno, fazendo com que demore um tempo arbitrariamente longo. Ou seja, a energia tempo (= ação ) necessária para executar um cálculo reversível pode ser constante. Este não é o caso de cálculos não reversíveis.$\times$

Muitas das pessoas que estudam nesta área também estão trabalhando em computação quântica e física digital (a idéia de que o universo é um grande autômato celular quântico). Os nomes dos pesquisadores que vêm à mente são Ed Fredkin , Tommaso Toffoli e Norm Margolus .

Essas perguntas são absolutamente sobre o tópico da ciência da computação. Não apenas para a teoria (que inclui matemática legal e física legal), mas também para engenheiros que desejam conhecer os limites finais da computação. Existe um volume ou energia mínima necessária para armazenar um pouco de informação? A ação necessária para executar um cálculo reversível pode ser constante, mas existem limites para o que é essa constante? Esses são conhecimentos críticos para os engenheiros que tentam ultrapassar os limites do que é possível.

Eu não sou familiar com o Teorema de Carnot, exceto o que acabei de ler na Wikipedia, mas mesmo a partir dessa introdução superficial, há uma conexão na estrutura das provas, e isso pode ser interessante para você, pois é uma técnica de prova isso é aplicável em muitos domínios.

Ambas são provas por contradição para mostrar que nada em uma determinada classe tem alguma propriedade; você supõe que alguma instância realmente tenha essa propriedade e depois mostra que uma contradição se segue.

O Problema da Parada é interessante, pois a contradição surge de alguma auto-interação referente à instância específica (que é uma máquina M que pode determinar se uma máquina arbitrária será interrompida com uma determinada entrada). Em particular, você constrói uma nova máquina que inclui M como componente e, em seguida, alimenta a nova máquina com M.

Alguém com mais conhecimento sobre o Teorema de Carnot poderia elaborá-lo (o que não estou qualificado para fazer), mas parece que a contradição decorre do tipo de motor térmico que você poderia construir se tivesse uma instância com a propriedade em questão.

Portanto, ambos os casos envolvem a construção de:

• Suponha que algum X tenha a propriedade P.
  • No X, construa Y relacionado.
  • As relações entre X e Y são contraditórias.
• Portanto, nenhum X tem propriedade P.

Parece haver uma diferença, no entanto, na medida em que a contradição no caso do Teorema de Halting é uma pura contradição lógica, e seria contraditória em qualquer cenário da lógica clássica. O Teorema de Carnot, como eu o entendo, é apenas contraditório em relação à segunda lei da termodinâmica. De uma perspectiva lógica, esse é um axioma; portanto, se você adotasse uma axiomatização diferente na qual a segunda lei da termodinâmica não se aplica, o Teorema de Carnot não seria um teorema, porque a contradição não existiria. (Como seria uma formalização da termodinâmica sem a segunda lei é o tipo de pergunta que levou os geômetros à geometria não-euclidiana.)

IANAPhysicist, mas não vejo nenhuma conexão. As máquinas de Turing são objetos de matemática pura e a indecidibilidade do problema da parada é independente de qualquer realização física de qualquer coisa.

essa questão diversa de múltiplos tópicos não tem uma resposta simples / fácil e toca em áreas ativas da pesquisa da TCS. no entanto, é uma pergunta rara fazer uma ligação entre a física e o TCS que me interessou ao longo dos anos. existem algumas direções diferentes para fazer isso. a resposta básica é que é uma "questão em aberto", mas com alguma pesquisa ativa / moderna tocando nela e sugerindo conexões.

• existem alguns problemas indecidíveis surpreendentes / profundos da física avançada. por exemplo, de sistemas dinâmicos. no entanto, não temos visto isso conectado à entropia em si, mas a entropia está associada a todos os sistemas físicos (por exemplo, pode-se ver isso na teoria da química), portanto, deve haver pelo menos um link indireto.

• de fato a entropia aparece no CS, mas mais na forma de teoria da informação e teoria da codificação. o nascimento da teoria da codificação envolveu a definição / análise da entropia associada aos códigos de comunicação por Shannon. experimente esta excelente referência online Entropia e teoria da informação por Gray

• a entropia também é associada às vezes associada à medição da aleatoriedade nos PRNGs. existe uma conexão de separações de classes de complexidade (por exemplo, P =? NP) com PRNGs no famoso artigo "Natural Proofs" de Razborov / Rudich. há pesquisas contínuas sobre esse assunto.

• você menciona termodinâmica e sua conexão com o TCS. existe uma conexão profunda entre magnetização em óculos de spin em física e problemas completos de NP estudados no ponto de transição SAT. lá (novamente) o sistema físico tem uma entropia associada, mas provavelmente foi estudado mais em um contexto de física do que em um contexto de TCS.

Há um problema de pensamento simples que às vezes é usado como uma introdução aos paradigmas de computação não convencionais:

Você tem duas lâmpadas e seus respectivos interruptores. Alguém abre e fecha as duas luzes uma após a outra. Como você determina qual foi fechado primeiro e qual foi fechado por último? Determine o número mínimo de vezes que você precisará abrir as luzes para decidir esse problema.

A maioria dos cientistas da computação geralmente tenta encontrar alguma solução booleana baseada em lógica. A resposta é (pelo menos uma delas): tocando as lâmpadas e vendo qual delas é mais quente.

Existem paradigmas baseados em calor na ciência da computação: o recozimento simulado é um algoritmo conhecido (o computador quântico de ondas D é a contrapartida quântica do algoritmo).

Agora existe uma relação com o problema da parada?

O trabalho clássico de Chaitin e Calude sobre o problema de Halting, através do conceito de números Omega, pode ser associado à formulação probabilística do problema de Halting. É o tratado mais recente sobre o problema em que consigo pensar ... e nenhuma relação clara com a entropia (termodinâmica). Agora, se a entropia da informação (no sentido de Shannon) é boa para você, o número Omega codifica da maneira mais sucinta o problema da parada, no sentido de um limite de Shannon.

Em resumo, um número Omega é a probabilidade de um programa aleatório ser interrompido. Conhecer a constante permitiria a enumeração de todas as declarações matemáticas válidas (verdades, axiomas etc.) e é incontestável. Calude calculou uma versão do Omega alterando a medida de probabilidade uniforme com uma medida inversamente proporcional ao comprimento de um programa aleatório e usando codificações sem prefixo.

Sim !, por incrível que pareça, pensei sobre isso. Aqui está a idéia:

Primeiro passo

Modele o Demônio de Maxwell como um programa de computador. Então, como o Demon conheceu a velocidade e a posição das partículas antes de abrir a porta para a seleção?

Suponha que o demônio não possa medir a velocidade com que as partículas atingem a porta, por quê? porque isso mudaria a velocidade das partículas, então o demônio precisa descobrir antes de abri-lo, sem olhar, sem medir. Para ser justo, vamos deixar o demônio conhecer as regras do jogo com antecedência, ou seja, alimentar o demônio com leis do movimento, interações de partículas e condições iniciais, o suficiente do modelo físico / dinâmico.

Segundo passo

Agora modele o gás das partículas também como um programa de computador que executa o mesmo código dado ao demônio para cada partícula, para que o gás esteja computando um resultado de suas condições iniciais, o Demônio não sabe o resultado até que ele pare (se é que alguma vez ): ou seja, "uma partícula com a velocidade certa está na porta", a decisão que está perguntando sim / não ao sistema é "Tem uma partícula na posição correta e com velocidade suficiente?"; nesse caso, a porta pode ser aberta e a partícula rápida pode entrar no lado de alta temperatura da sala, estabelecendo novas condições iniciais (esses problemas consecutivos terão uma resposta? ou serão executados para sempre?)

Haverá um tempo em que não haverá partículas com velocidade suficiente para ultrapassar os limites; portanto, haverá um tempo em que o código será executado para sempre (não pare) para quase qualquer limite.

Demon quer saber o resultado que é calculado pelo gás, mas o resultado está, de certo modo, envolvido potencialmente dentro do código fonte das leis das partículas, além das condições iniciais. É claro que precisamos executar esse programa para conhecê-lo. Se o Demon executar o mesmo programa aguardando a velocidade correta na saída, o programa poderá parar ou poderá ser executado para sempre (mas supomos também que o demon não tenha mais poder computacional que o gás, portanto, não poderá decidir o abertura da porta a tempo).

O Daemon pode tentar descobrir a saída do programa (ou se será interrompido) observando a fonte e as entradas sem executá-lo, mas é como tentar resolver o Problema da Parada, por que? porque o Demon não sabe quais leis e condições iniciais serão alimentadas, então o Demon deve estar preparado para resolver qualquer conjunto de leis e condições iniciais, e sabemos que não é possível em geral, ele precisará de um oráculo, se puder basta construir um demônio para gerar energia do nada. (mesmo conhecendo as leis e a condição inicial, as duas coisas já são difíceis de saber)

Esse experimento mental pode vincular como uma redução na entropia, por meio de computadores, poderia de alguma forma delimitada pelo Halting Problem , como um problema para antecipar os resultados em geral.

(Às vezes, todos os limites parecem ser o mesmo limite.)

Mais sobre Leis de Partículas

As leis de partículas não são a questão principal desse experimento mental, essas leis podem ser quânticas ou clássicas, mas devemos ter em conta o fato da complexidade das leis e das condições iniciais, a complexidade do arranjo das partículas não é limitada e poderia tem muita complexidade adicional (em um exemplo extremo de condições iniciais, você pode até inserir um computador inteiro disparando partículas de acordo com um código-fonte interno e fornecendo esse código ao daemon).

Uma pergunta muito cativante, e veremos que seu pensamento está correto .

Primeiro vamos ver o que diz o segundo princípio da termodinâmica.

A função entropia é usada na 2ª lei da termodinâmica. Ela deriva do teorema de Carnot, que afirma que os processos que ocorrem em máquinas a vapor têm uma eficiência menor ou, na melhor das hipóteses, igual à correspondente máquina "reversível" (que, a propósito, parece um conceito instável ao longo dos 150 anos de termodinâmica). Carnot não cunhou a função de entropia, mas junto com Clausius é o que eles dizem:

Como não há máquina de perpetuo, podemos construir uma função S chamada entropia que restringe medidas termodinâmicas macroscópicas a uma determinada equação, a saber: S (V, T, P, etc.) = 0

Note que esta equação nada mais é do que a equação de uma hiper-superfície no espaço de medidas termodinâmicas.

Entra no Carathéodory.

Carathéodory é um matemático alemão e, como todos os matemáticos, deseja extrair de Carnot e Clausius raciocinando alguns axiomas que lhe permitiriam esclarecer o que realmente é a segunda lei . Em outras palavras, ele quer purificar a termodinâmica para saber exatamente o que é entropia.

Depois de listar um certo número de axiomas, ele consegue formular sua segunda lei, que diz (mais ou menos):

Existem alguns processos adiabáticos. Ou, mais prosaicamente, se você deseja retornar, às vezes trabalhar sozinho não é suficiente. Você precisa de um pouco de calor.

Agora isso parece MUITO diferente da formulação de Clausius! Mas, na verdade, não. Tudo que Carathéodory fez foi mudar a ordem das palavras, um pouco como os matemáticos brincaram com o quinto axioma de Euclide por 2.000 anos e produziram muitas palavras diferentes para esse axioma. E se você der um passo atrás, não ficará surpreso com a declaração da segunda lei de Carathéodory. De fato, o de Carathéodory leva à mesma função de entropia e à equação de hiper-superfície S (V, T, P, etc.) = 0

Pense bem no teorema de Carnot. Como matemático, você não deve estar muito satisfeito com a forma como a Carnot's admite que as máquinas de perpetuum não existem. De fato, como matemático, você prefere ver algo assim:

Existe uma função de entropia S que restringe medidas macroscópicas SE E SOMENTE SE NÃO houver máquinas de perpetuo ".

AGORA você tem um teorema. E o que isso diz? Que, desde que não exista um sistema mecânico isolado que produza uma quantidade infinita de energia e, portanto, possa levá-lo a qualquer estado desejado, você encontrará uma função de entropia. Um sistema mecânico isolado é um processo adiabático. Daí a formulação de Carathéodory: nenhum sistema adiabático pode levá-lo a qualquer lugar. Às vezes você precisará de um pouco de calor.

Portanto, não apenas temos certeza de que Carathéodory está correto, mas também que sua formulação é bastante simples.

Agora, onde você tem a impressão de que a segunda lei à la Carathéodory é semelhante ao problema da parada?

Dê um passo atrás na declaração de Carathéodory. Tudo o que diz é que, uma vez que você tenha um sistema mecânico isolado com o qual para de se misturar, não poderá alcançar o estado que deseja.

Não soa PRECISAMENTE o problema da parada? Ou seja, depois de escrever todos os axiomas de sua teoria e estabelecer todas as transições possíveis, haverá problemas que você não poderá resolver. Às vezes, você precisará adicionar mais axiomas.

De fato, se você quiser se aprofundar e codificar a formulação de Carathéodory, isso resultará no mesmo código que o problema de parada com processos adiabáticos em vez de máquinas de Turing e estados em vez de problemas.

O que você acha?

NOTA: editei quase totalmente minha resposta para que os comentários abaixo não estejam alinhados com o que ela contém agora.