Problemas indecidíveis limitam teorias físicas

A existência de problemas indecidíveis implica imediatamente a imprevisibilidade dos sistemas físicos? Vamos considerar o problema da parada, primeiro construímos um UTM físico, digamos usando a construção habitual baseada em circuito. Então não pode haver uma teoria física decidível que possa determinar, dada qualquer configuração de entrada dos circuitos, se o circuito irá parar. Isso parece uma trivialidade, mas isso não nos dá um tipo fraco de imprevisibilidade sem referência a considerações quânticas ou caóticas? Além disso, podemos fortalecer o argumento acima observando que não há nada de especial no UTM baseado em circuito; portanto, temos que o comportamento de um sistema físico é geralmente indecidível em qualquer nível em que um UTM possa ser construído.

Edit: como apontado por Babou e Ben Crowell, minha construção de circuito sugerida é apenas um LBA. Como argumentei nos comentários, acho fácil e intuitivo imaginar uma máquina que é física, mas não é linearmente limitada. Simplesmente construa uma máquina (robô) que pode mover-se mecanicamente para a esquerda / direita em uma entrada arbitrariamente várias vezes e suponha que ela tenha uma fonte de energia finita, mas não expirada. Agora, também nos deparamos com o problema de que o universo é finito, mas isso nos permite concluir que o universo é finito ou que a conseqüência originalmente esperada deve ser verdadeira (isso ainda seria uma conclusão surpreendente a partir do argumento acima) .

Inicialmente, isso foi planejado como um comentário, pois contorna um pouco a questão. Mas acho que responde da sua maneira.

O que se sabe, ou tenta-se até agora, mostra que conectar a teoria da computação à física pode ser um empreendimento bastante sutil, e receio que a abordagem sugerida na pergunta seja provavelmente um pouco grosseira. Não tenho certeza de que seja muito melhor do que o argumento clássico de que, tudo sendo finito, tudo o que precisamos é da teoria dos autômatos de estados finitos e que estudar as máquinas de Turing é uma perda de tempo. (Não é minha visão das coisas)

Por que essas questões devem ser tratadas com cautela

Eu provavelmente deveria motivar a comparação acima com o argumento de autômatos finitos. Minha percepção é que a computabilidade é, talvez até mais que a complexidade, uma teoria assintótica: o que importa é o que ocorre no infinito. Mas não sabemos se o universo é finito ou infinito. Se for finito, qual seria o ponto de considerar cálculos infinitos. O que se segue diz respeito à física, e eu não sou físico. Faço o possível para ser preciso, mas você foi avisado .

Muitas vezes vemos o Big Bang como um "tempo" em que todo o universo era uma coisa muito pequena, com um tamanho muito pequeno. Mas se ele tivesse um tamanho em algum momento, como se transformaria em algo infinito posteriormente? Não estou tentando dizer que é impossível ... Não tenho a menor idéia. Mas pode ser que sempre tenha sido infinito.

$r$$r$devido à expansão é igual à velocidade da luz. De acordo com o que sabemos atualmente, sem uma variação futura na velocidade de expansão, nada fora dessa esfera será motivo de preocupação para nós. Portanto, o universo é finito para nós para todos os fins práticos. Na verdade, as coisas são ainda piores se você considerar o conteúdo desse universo relevante: está encolhendo (a menos que haja algum processo de criação). A razão é que a esfera está se expandindo além de seu próprio diâmetro, levando consigo parte de seu conteúdo que também se torna irrelevante. Observação: essa esfera não é o que é chamado de universo observável (que depende da idade do universo), é muito maior.

Assim, não apenas o universo "nosso" é finito, mas seus recursos podem estar encolhendo. É possível que, em tantos bilhões de anos, apenas nossa galáxia ainda seja relevante para nós (supondo que ainda existamos), com a galáxia de Andrômeda, que atingirá a Via Láctea antes disso.

Bem, não sei o que é considerado estabelecido no momento, mas mostra pelo menos que assumir o infinito é uma grande suposição.

No entanto, as limitações físicas nos impedem de usar a teoria da computabilidade. Tudo o que se pode concluir a partir do exposto acima é que pode não ser razoável extrair conclusões físicas do trabalho teórico sobre Máquinas de Turing e do problema de parada.

No entanto, as técnicas em questão também podem fornecer resultados úteis quando aplicadas a dispositivos ou formalismos que não são completos para Turing. Eu não tentaria entrar em detalhes, nem que seja porque a complexidade algorítmica não é minha área, mas suponho que, se a estrutura do universo for discreta, a complexidade poderia ser de alguma forma relevante para o comportamento de alguns fenômenos. Claro, isso é apenas especulação selvagem da minha parte. Algumas das pesquisas que refiro a seguir estão relacionadas a esses problemas de discrição.

Alguns exemplos de trabalhos relacionando física e teoria da computação

Há um corpo significativo de trabalho tentando amarrar computação e física, a maioria das quais eu mal conheço. Portanto, não confie em nada que eu possa dizer , mas use -o como ponteiro para procurar trabalho potencialmente relevante.

Boa parte desse trabalho está relacionada a aspectos termodinâmicos, como a possibilidade de computação reversível sem custo de energia. Eu acho que isso está relacionado à programação funcional, pois os efeitos colaterais custam energia (mas não confiam em mim). Você pode usar a wikipedia como introdução, mas o Google produzirá muitas referências .

Há também trabalhos que tentam vincular a tese e a física de Church-Turing, envolvendo densidade de informações, entre outras coisas. Veja por exemplo:

• A tese física de Church-Turing e os princípios da teoria quântica

• Em torno da tese da igreja física de Turing: autômatos celulares, línguas formais e os princípios da teoria quântica ,

• Tese de Física e Igreja-Turing .

Lembro-me vagamente de ter visto outras perspectivas interessantes sobre isso, mas agora me escapa.

Então você tem o trabalho de Lamport sobre sincronização e relatividade de relógios em sistemas distribuídos .

E, é claro, você tem computação quântica que aparentemente altera algumas complexidades de tempo (alcançáveis), embora isso não afete a computabilidade.

Outro ponto é o trabalho de Wolfram na modelagem de leis físicas com autômatos celulares , embora os benefícios reais desse trabalho pareçam controversos.

Eu acho que tentar entender todo esse trabalho pode levá-lo mais perto de entender como você pode vincular algum conhecimento de computabilidade com (como implicando) limitações teóricas do mundo físico, embora a tendência até agora fosse mais vincular as limitações de computabilidade (como conseqüências de) propriedades do universo físico.

Um possível problema em tudo isso é a auto-incorporação de todas as nossas teorias (matemática, computação, física, ...) dentro dos limites de conceitos sintaticamente expressáveis ​​(ou seja, por uma linguagem) que podem estabelecer um limite para o poder expressivo da nossa ciência. Mas não tenho certeza se a frase anterior tem significado ... desculpe-me por isso, é o melhor que posso fazer para expressar uma dúvida incômoda.

Como motivo de decepção pessoal , eu acrescentaria que os físicos (pelo menos em http://physics.stackexchange.com ) não são muito amigáveis ​​para discutir o que outras ciências poderiam ter a dizer sobre questões físicas (embora estejam dispostas a discutir o que a física pode ter a dizer sobre outras ciências).

A pergunta pergunta em parte sobre a imprevisibilidade dos sistemas físicos . A indecidibilidade aparece em alguns problemas de física. Uma pesquisa inicial feita por Wolfram, Indecidibilidade e Intratabilidade em Física Teórica (ou aqui ) e essa área continua a se expandir. No entanto, uma maneira melhor de entender a imprevisibilidade inerente física é mais através do que é conhecido como "dependência sensível das condições iniciais", também conhecido como efeito borboleta . Isso pode ser estudado usando o atrator Lorentz como modelo semi-brinquedo.

A pergunta é interessante (você pode verificar uma pergunta relacionada "Existe uma conexão entre o problema de parada e a entropia termodinâmica?" )

O núcleo do problema é o que vem primeiro na matemática ou na física? Bem, a física é a resposta . A citação de Einstein diz: " o tipo de matemática que fazemos, depende do mundo em que vivemos " (se não estou enganado este é de "Einstein, Filósofo-Cientista") (e outro relacionado, e um pouco parafraseado " A natureza faz não se preocupam com nossas dificuldades matemáticas. Ele se integra empiricamente " ). Portanto, nesse sentido, certas características físicas são refletidas no simbolismo e procedimento matemáticos. Mas também se pode adotar a visão oposta de que a matemática define física (uma visão bastante popular em certos círculos).

Há uma passagem na introdução do livro "Álgebra Linear" de J B. Fraleigh, R. A. Beauregard (um bom livro sobre o assunto e um ponto que eu queria abordar, dada a oportunidade)

Os números existem apenas em nossas mentes. Não existe uma entidade física que seja o número 1. Se houvesse, eu estaria em um lugar de honra em algum grande museu da ciência e, no passado, apresentaria um fluxo constante de matemáticos olhando para 1 com admiração e admiração.

No entanto, isso não é verdade , há realmente algo que experimentamos e é um (literalmente) , o sol (não cuide das estrelas à noite nem da lua, que não é percebida como uma em todas as circunstâncias, o sol, o único visível) coisa no céu à luz do dia). (e de fato tem sido historicamente um objeto de honra e reverência da humanidade). Pode-se continuar e discutir outras coisas que experimentamos como dois ou três e quatro ( duas mãos, cinco dedos e assim por diante), mas o ponto principal foi dado (para mais informações, procure por " pré-histórico e histórico de sistemas numéricos" ")

Diga por um minuto que um resultado matemático declararia algo, mas então uma teoria física forneceria um procedimento para alcançar o oposto (efetivamente uma prova construtiva do oposto). Então algo estaria errado, eles são relacionados principalmente quando usam exatamente o mesmo formalismo. É intuitivo que estes estejam relacionados de alguma forma.

Por exemplo, um resultado matemático de impossibilidade limitaria a descrição matemática de uma teoria física que precisaria desse resultado e assim por diante. Um exemplo que eu posso usar agora é a chamada "teoria de tudo". Supõe-se que descreva em forma matemática todas as interações físicas que ocorrem, para que, na verdade, descreva tudo. No entanto, pelo teorema de Goedel, sabe-se que essa descrição seria incompleta em um sentido ou outro. Isso diz algo sobre o mundo em que vivemos? Muito provavelmente.

Mas os resultados da imposibilidade são conhecidos em termos puramente físicos e a maioria deles está relacionada à termodinâmica. Por exemplo "O calor flui do quente para o frio". Este é um resultado de impossibilidade. Mas isso também limita qualquer resultado matemático que implique (quando aplicado no contexto apropriado) que o calor flua do frio para o quente , isso não acontece. Portanto, a matemática pode ser limitada por termos físicos . A verdadeira questão é qual é a conexão exata (se houver) entre esses dois e esta é uma pergunta muito interessante, com resultados interessantes e de longo alcance. Por exemplo, você pode verificar o trabalho de G. Chaitin, que relaciona a teoria da informação, os teoremas de Goedel e os sistemas biofísicospara começar. Algumas outras conexões já foram mencionadas, como computação reversível, computação quântica e assim por diante.

Por último, mas não menos importante, lembre-se de que a física depende de experimentos para formular e verificar coisas, e não de provas simbólicas . (A) A descrição matemática de uma teoria física é importante em termos de cálculos; portanto, uma matemática problemática pode limitar ou causar problemas no poder de cálculo da teoria; o experimento permanece. E lembre-se de que os físicos geralmente estão entre os criadores da nova matemática, conforme necessário (por exemplo, Cálculo e Equações Diferenciais, Probabilidades, Análise de Tensores, Procedimento de renormalização na mecânica quântica, Regularização analítica e assim por diante).

No que diz respeito ao seu exemplo de conexão da imprevisibilidade a uma TM, a conexão pode ser feita e pode exigir uma fita ilimitada, desde que a máquina precise calcular com precisão infinita (ou seja, números irracionais / transcendentais que não são de forma alguma excluídos de um físico) sistema). Então, uma máquina LBA não será poderosa o suficiente para calcular um determinado sistema físico e a pessoa entrará na fita UTM infinita que tem um problema de parada. A questão de saber se a imprevisibilidade pode ser atribuída às condições iniciais (a definição formal ensinada de comportamento caótico) ou a própria computação não é essencial, uma vez que apenas transfere o problema para outro lugar, em vez de corrigi-lo.

Babou,

É realmente uma pergunta muito interessante, mas, como dito acima, muita literatura foi produzida sobre o assunto. O mínimo que você pode dizer depois de ler tudo isso é que o mapeamento do UTM para sistemas físicos está longe de ser direto - por mais sedutora que seja a idéia.

Pessoalmente, gosto de começar do conceito de computação reversível introduzido por Landauer e mencionado nas respostas anteriores. Parece haver uma conexão conceitual entre entropia e UTM.

Pense da seguinte maneira: imagine que você deseja caminhar do ponto A ao ponto B (geograficamente distinto) usando um plano determinístico (isto é, uma série de etapas que podem ser anotadas com antecedência como um UTM: caminhe direto por 100m, vire à direita na a padaria, caminhe 50m etc.). Você pode andar a distância uma vez. Duas vezes. Três vezes. Quantas vezes você pode fazer isso? A menos que você inclua um estoque infinito de comida e água em seu plano, terá que parar após um número finito de viagens. Porém, embora uma fita UTM seja infinita, o número de etapas da própria TM deve ser escrito em um número finito de caracteres. Portanto, seu plano não pode incluir uma quantidade infinita de comida e água.

Agora a energia é uma quantidade conservadora. Então você pode pensar que uma quantidade finita de provisões deve ser suficiente. Mas claramente este não é o seu problema aqui. Mesmo se você viajar muito devagar entre A e B, seu corpo transformará sua comida em algo que você não pode mais consumir. Observe que se você tentar escapar desse problema e for INFINITEMENTE devagar (quase estaticamente entre A e B), não poderá mais escrever seu "plano" com um número finito de caracteres. Portanto, é o aumento da entropia termodinâmica (degradação da comida e da água através do processamento do seu corpo) que parece limitar o número de viagens que você pode fazer enquanto segue um plano determinístico (por exemplo, um UTM).

Se isso estiver correto, a imprevisibilidade da MT deve ser mapeada para o aumento da entropia termodinâmica.Observe como isso parece bastante contra-intuitivo (como dito anteriormente, esse tipo de mapeamento está longe de ser trivial): para o infinito, o aumento da entropia termodinâmica leva a um equilíbrio, ou seja, algo estável; mas o mesmo limite infinito do UTM correspondente leva a um comportamento aleatório (ou seja, não temos certeza de que tipo de saída). Isso é ainda mais impressionante com uma bola rolando em uma curva convexa com atritos: a entropia termodinâmica faz a bola parar no ponto mais baixo da curva, o que é algo bastante fácil de prever; mas o UTM equivalente informará que "algo aleatório" acontece no final, o que não pode ser previsto. Será que temos que mapear essa imprevisibilidade para o movimento aleatório de átomos criado pela dissipação de calor do movimento da bola contra a superfície da curva? Este'

Espero que ajude!

Eu acho que um bom modelo para isso é o jogo da vida de Conway.

Desde que inventamos as regras, nós as conhecemos perfeitamente. Isso é análogo a uma teoria física.

No entanto, apesar de quão simples são as regras e do fato de conhecê-las, a vida é indecidível .

Da mesma forma, mesmo se aprendêssemos todas as leis da física, pode ser que elas também sejam indecidíveis.

Não há realmente nada que você possa fazer sobre isso. Porém, uma coisa a ter em mente é que você pode prever o jogo da vida de Conway para qualquer número finito de etapas . Isso pode ser o mesmo para a física.

A existência de problemas indecidíveis implica imediatamente a imprevisibilidade dos sistemas físicos?

Não.

primeiro, construímos um UTM físico, digamos, usando a construção habitual baseada em circuito.

Uma máquina universal de Turing é uma máquina de Turing. Uma máquina de Turing possui uma fita infinita (ou infinitamente extensível). Portanto, você não pode construir um fora dos circuitos. O que você pode construir é um autômato limitado linear (LBA).

Então não pode haver uma teoria física decidível que possa determinar, dada qualquer configuração de entrada dos circuitos, se o circuito irá parar.

O problema de parada é decidível para um LBA, portanto, seu argumento falha.