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

31

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

Nikos M.
fonte
1
há um sentido em que os conceitos delineados são exatamente opostos . as leis da dinâmica da dinâmica da ascensão da entropia excluem uma máquina de movimento perpétuo . uma máquina não asfaltada é uma máquina de movimento perpétuo .
vzn
Sim, entendo, refazer a condição sem interrupção como móvel perpétuo (do 2º tipo?), isso está exatamente no espírito da pergunta, mas é isso que o teorema da parada diz? Ele afirma que não sabemos se ele pára ou não, devido a "circularidade", agradável
Nikos M.
Uma proposta para adicionar "termodinâmica" e / ou "computação termodinâmica" como novas tags no CS.se? Eu não tenho certeza se eu posso fazer isso por mim (provavelmente), mas vamos ouvir outras opiniões
Nikos M.

Respostas:

11

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.×

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.

Lógica Errante
fonte
Sim, há uma relação com a termodinâmica da computação (Bennett, Landauer et al.), Mas perguntando mais em relação ao teorema da parada e / ou mapeamento entre MT e CE (como em questão), mas uma boa resposta
Nikos M.
1
Ah, você está certo. Estou votando negativamente na minha resposta. Os comentários em sua pergunta dizendo que estava fora do tópico me fizeram ver vermelho, e eu estava principalmente respondendo a isso. Em resposta à sua verdadeira pergunta: veja a Tese de Church-Turing. Supondo que você acredite nisso e também que a matemática possa modelar qualquer coisa da natureza, o Problema da Parada é um teorema da impossibilidade física.
Wandering Logic
eu acho que a tese de Church-Turing que a computação física é eficaz computação pode ser necessário, de fato, dê uma olhada neste artigo também
Nikos M.
5

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.)

Joshua Taylor
fonte
este artigo fornece muito na direção que você menciona, imo. Também o que eu acho que é muito relevante é a circularidade (ou diagonalização) dos argumentos. Existem instruções de pesquisa que conectam transformações lógicas irreversíveis a processos termodinâmicos irreversíveis (por exemplo, o princípio de Landauers e suas objeções). Há objeções a algumas declarações da 2ª Lei, mas pode-se encontrar formulações que ainda detêm (por exemplo, a obra de Prigogine)
Nikos M.
Por quanto essa conexão pode vir sobre ver também comentários sobre a resposta anterior (apenas para fins de plausibilidade)
Nikos M.
Em relação a outras formulações da 2ª Lei (ainda mais gerais e para processos de desequilíbrio), você pode verificar a declaração de Caratheodory em termos de espaço de fase e geometria, o trabalho de Prigogin sobre sistemas de não equilíbrio e a formulação de Hatzopoulos-Gyftopoulos-Beretta (com conexões adicionais a mecânica quântica)
Nikos M.
Em certo sentido, há tantas facetas da entropia como existem facetas do teorema de Gödel (s) (como na teorema de parada de Turing, teorema undefinability de Tarski , teorema de Rosser , do Chaitin teorema da incompletude ), há ainda uma prova da categoria-teórica de um "general Gödel Teorema", abrangendo todos os anteriores, que é baseada em pontos fixos
Nikos M.
Mesmo que uma conexão entre o problema de interrupção e a entropia termodinâmica seja alcançada na forma de se e quando a Lei 2md é válida ... , ainda é tão boa quanto esta pergunta (relacionada à objeção de que a 2ª Lei pode ser como a 5 postulado em paralelos na geometria euclidiana)
Nikos M.
4

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.

David Richerby
fonte
Os resultados da 2ª Lei da Impossibilidade têm muito em comum com problemas e circularidades da lógica (matemática), talvez uma conexão aí?
Nikos M.
1
Você teria que dar mais detalhes: como eu disse, não sou físico. Mas não vejo como as leis físicas podem ter impacto em uma construção que existe independentemente da realidade física.
David Richerby
você tem um argumento aí, posso dar muitas razões epistemológicas pelas quais isso é muito plausível (por exemplo, a matemática em que dependemos do mundo em que vivemos , a-la Einstein), mas quero algo além disso, se tivesse uma resposta pronta. provavelmente publicar um artigo :)
Nikos M.
2
@vzn Usamos a palavra "tempo" para o número de etapas que a máquina executou e "espaço" para o número de células de fita usadas, mas essas palavras foram escolhidas para apelar à nossa intuição física como seres físicos. Mas "tempo" é apenas um índice em uma sequência de configurações e espaço é apenas um índice em uma sequência de símbolos. Por exemplo, considere uma máquina de Turing em que a cabeça apenas gire para a direita. Ele usa infinita "tempo" e "espaço" infinito, mas você pode descobrir isso em uma quantidade finita de tempo real e espaço real
David Richerby
2
Claro, mas o fato de considerarmos as máquinas de Turing objetos interessantes pode ter algo a ver com a física.
Gilles 'SO- stop be evil'
1

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.

vzn
fonte
pode expandir um pouco dessa longamente em Ciência da Computação via Chat
vzn
veja também CS defn de entropia stackoverflow
vzn
é interessante poder pensar "pronto para uso" (pelo menos algumas vezes), você analisou o trabalho de Bennet sobre Termodinâmica da Computação? A motivação por trás da pergunta é mostrar se o teorema da parada pode ser visto como uma conseqüência da termodinâmica (com algum modelo ou representação apropriada, pelo menos em alguns casos). eu acho que seria realmente interessante se isso poderia ser resolvido de qualquer maneira
Nikos M.
Talvez você já tenha visto estes papéis, philsci-archive.pitt.edu/313/1/engtot.pdf e cc.gatech.edu/computing/nano/documents/...
Nikos M.
A maioria dos conceitos de "entropia", usada na ciência da computação, está relacionada à Teoria da Informação de Shannon ou à Teoria da Informação Algorítmica de Kolmogorov / Chaitin / Solomonov, isso já é mencionado na pergunta e é muito importante. As únicas conexões com a entropia termodinâmica que eu conheço (que podem estar relacionadas à entropia de informações) são as termodinâmicas da computação. A questão está relacionada com a termodinâmica da computação, mas de outra maneira
Nikos M.
1

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.

user13675
fonte
Boa resposta, a parte relacionada ao calor das lâmpadas é usada muitas vezes como o elo entre a entropia da informação e a entropia termodinâmica (é um sentido contrário à visão de Jaynes como incerteza subjetiva). minha própria linha de pensamento seria basear o raciocínio sobre a circularidade de ambos os construtos e por um (inteligente?) uma cascata com outro criar uma implicação (pelo menos de uma forma)
Nikos M.
Um raciocínio semelhante é usado com baterias (em vez de lâmpadas) para determinar quais baterias estão descarregadas ...
Nikos M.
0

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).

Hernan_eche
fonte
1
Não entendo o link para o problema da parada. Primeiro, você parece ter redefinido o que significa para uma máquina parar. Segundo, você parece ter apenas um programa (o simulador de partículas de gás). É perfeitamente possível provar que um programa fixo interrompe ou não, sem violar a indecidibilidade do problema geral de interrupção.
David Richerby
Sobre parada, não redefiniu a parada, aqui o programa é, como sempre, quando o programa termina a computação e você obtém uma saída, então aqui a saída é definida como o momento exato em que uma partícula com a velocidade certa bate na porta , e você pode criar uma porta que a detecte, para marcar quando o programa for interrompido (o programa será executado novamente a partir dessas condições iniciais para outra saída). Daemon quer saber quando será interrompido, mas não poderá saber nem mesmo se será interrompido.
21714 Hernandy_Henry_eche
1
As máquinas de Turing não podem decidir o problema de parada das máquinas de Turing. Parece que você redefiniu o problema de parada como "Uma dessas moléculas de gás faz X?", Que é um problema completamente diferente de "Esta máquina de Turing para quando inicia com essa entrada?" Prova da indecidibilidade do problema máquina parada Turing de Turing diz nada sobre se uma máquina de Turing pode calcular se alguma molécula de gás nunca vai fazer X.
David Richerby
O comentário de David está correto, como está, não está diretamente relacionado ao problema da parada. No entanto, é um argumento que segue o espírito da questão
Nikos M.
1
@Gilles, obrigado por observar que, eu concordo com isso, se necessário, um bate-papo será criado. Eu preferiria se esses comentários foram deixados no entanto, uma vez que se relacionam tanto com a pergunta ea resposta específica (como evoluiu)
Nikos M.
-1

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.

Jerome
fonte
1
"Rice afirma que nenhuma máquina de Turing pode produzir indefinidamente uma propriedade não trivial". Essa não é uma paráfrase de Rice que reconheço. O que você quer dizer?
precisa saber é o seguinte
1
O que você quer dizer com "produzir infinitamente uma propriedade não trivial"?
David Richerby
Um pouco torcido. Rice diz que não se pode provar que uma TM implementa uma determinada função. Agora, se uma TM A produz indefinidamente uma propriedade não trivial (N-TP), significa que produz uma N-TP para QUALQUER entrada. Como isso pode ser verdade na prática? Bem, parece que a única maneira de isso ser verdade é considerar uma entrada indefinida e e mostrar que seu A (e) possui um N-TP. Por sua vez, isso significa que conseguiríamos provar que a máquina produz um N-TP. E sabemos que isso não é possível. Então, na verdade eu postular que é equivalente a dizer "A produz indefinidamente uma N-TP" e "Eu posso mostrar que A produz um N-TP"
Jerome
"Produzir infinitamente uma propriedade não trivial" significa que você pode lançar um número infinito de entradas distintas na TM. E todas as saídas terão o NT-P
Jerome
1
ESTÁ BEM. Eu acho que sua resposta seria muito mais clara se você usasse termos padrão, em vez de inventar coisas como "produzir infinitamente uma propriedade não trivial" para significar "ser capaz de processar um número infinito de entradas". Também ajudaria a explicar que aspecto da sua máquina de Turing "real" é incapaz de processar um número infinito de entradas. A fita é finita, por exemplo?
precisa saber é o seguinte