A insolubilidade do Problema do Corpo N é equivalente ao Problema da Parada

16

Não existe uma solução analítica geral para o problema do corpo n que possa produzir uma função analítica que possa ser usada para fornecer o estado de um sistema n corpo no tempo arbitrário t com precisão exata. No entanto, existem alguns casos especiais de sistemas com n corpos, pelos quais é conhecida uma função analítica.

Da mesma forma, não há algoritmo geral que possa prever o resultado de uma máquina de Turing arbitrária. Embora existam muitos tipos de máquinas de tornear que podem ser determinadas para parar ou funcionar para sempre.

Esses dois resultados são equivalentes? A prova de um deles implica o outro? Uma máquina mágica capaz de resolver o problema de parada seria capaz de prever o estado de um sistema de n corpos com precisão exata? Ou vice-versa, uma solução analítica geral para o problema do corpo n nos permitiria decidir o problema da parada em uma máquina de Turing arbitrária?

Meu palpite inicial sobre como abordar isso seria mostrar que um sistema de corpo n sob gravitação é Turing completo. Suspeito que esteja considerando que o universo é Turing completo e essencialmente opere sob gravitação (e algumas outras forças que se comportam de maneira semelhante), mas não tenho idéia de como provar isso.

Mas sou cético quanto a essa abordagem ser suficiente, considerando que eu acho possível (embora eu ache improvável) que a falta de uma solução geral analítica para o problema do corpo n possa ser independente da conclusão de Turing.

Edit: Depois de ler algumas outras questões relacionadas tangencialmente, percebi que o número de dimensões em que a gravidade está operando pode ser relevante para a questão. Estou perguntando especificamente sobre a gravidade em três dimensões espaciais. Porém, dados fatos como o de que você precisa de pelo menos três regras para criar uma máquina de Turing universal e a gravidade em duas dimensões teriam apenas uma lei inversa vez de uma lei quadrada inversa resultando em nenhuma órbitas fechadas , posso ver que a gravidade em três dimensões é Turing Complete, mas não em duas ou uma.∝ 1 / r 2∝1/r∝1/r2

computability turing-machines undecidability computation-models Shufflepants
fonte
1
É sua escolha fazer a pergunta que quiser, mas receio que você possa estar usando palavras e conceitos técnicos sem o menor cuidado para saber se eles podem ter significado no contexto em que você escolhe usá-los. Isso não é muito científico. Não estou dizendo que é errado especular, mas exige cautela. O que pode significar que um problema de n-corpo seja Turing completo? O que pode ser uma enumeração de Gödel de problemas no corpo? A propósito, Turing sempre escreve com T maiúsculo, devemos a ele pelo menos isso.
babou
Quero dizer que o problema do corpo n é Turing completo no mesmo sentido que o Jogo da Vida de Conway é Turing completo; que você pode configurar um sistema de partículas de pontos gravitacionais e usar a evolução do estado desse sistema para realizar cálculos.
Shufflepants
Não sei o que tudo poderia ser codificado na posição, velocidade ou aceleração de um número de partículas pontuais de massas variáveis ​​ou idênticas. Estou perguntando explicitamente se existe tal codificação porque não sei.
Shufflepants
1
O jogo da vida de Conway é um tipo de teoria de autômato celular, uma estrutura muito discreta, como máquinas de turing. Então, podemos imaginar que é possível codificar um no outro. Mas o problema do corpo n está em um mundo de equações diferenciais, funções contínuas e outras coisas ... Estou um pouco duvidoso em codificar um no outro. O que você pode esperar (embora eu duvide, e eu seja incompetente de qualquer maneira) é que a inexistência de uma solução analítica para o problema de n corpos seria conseqüência de uma contradição interna a qualquer teoria que possa expressar esse problema, um pouco como a prova do problema de parada.
babou
1
Na verdade, sua melhor chance é como um problema de matemática. Os físicos lhe dirão que o n corpo é caótico, sensível às borboletas, de modo que as flutuações quânticas matam qualquer codificação de longo alcance ou qualquer previsão da evolução do sistema, o que não é muito bom para uma máquina de Turing. O pessoal da matemática pode muito bem dizer algo pior, mas felizmente não sei o que é.
babou

Respostas:

9

Existe alguma pesquisa (um tanto dispersa) sobre a indecidibilidade do problema do corpo N da física (em consonância com o estudo geral de fenômenos indecidíveis na física clássica e quântica), que pergunta sobre o cálculo de trajetórias futuras ou órbitas de objetos todos sujeitos a interações gravitacionais; tem sido estudado há séculos, incluindo, por exemplo, Newton e Gauss. Basicamente, reduz-se a uma grande variedade de equações diferenciais e provou-se que esses sistemas contêm cenários de indecidibilidade. No entanto, esta é uma área transversal incomum da física e da matemática que não é amplamente citada em nenhum dos campos e também não parece haver referências únicas amplamente citadas.n2

Veja por exemplo

vzn
fonte
Não tive a chance de ler e entender completamente esse primeiro artigo, mas parece que provavelmente está o mais próximo possível de responder às minhas perguntas. Então, estou aceitando esta resposta.
Shufflepants