Problemas indecidíveis limitam teorias físicas

11

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

user2663116
fonte
1
Talvez seja mais adequado para a física ?
David Richerby
@DavidRicherby Os físicos consideram isso, na melhor das hipóteses, como uma questão de opinião. Infelizmente, não posso apontar para exemplos, pois eles os excluem. Esse é o ponto de vista deles, considerando que qualquer papel que a computabilidade possa desempenhar na teoria física, além de fornecer computadores a eles. Estou falando sério.
babou 24/05
1
@babou Os especialistas no comportamento do universo são físicos, não cientistas da computação. Se os físicos não acham que essa é uma pergunta "real", então temos um problema: os especialistas não consideram que vale a pena responder, portanto apenas as respostas de não especialistas permanecem.
David Richerby
3
Passei um tempo significativo escrevendo uma pergunta sobre um possível papel da teoria da computação na física teórica (não apenas como ferramenta computacional ou como ferramenta universal de modelagem sem perspicácia), solicitando referências publicadas publicadas. Foi rejeitado como "principalmente baseado em opiniões". E foi rapidamente excluído para que ninguém possa comentar ... recebi um ou dois comentários relevantes. Eu me pergunto do que eles têm medo. Mas isso me reforçou ao me recusar a tolerar o gatilho de políticas de fechamento feliz, especialmente com base em avaliações frágeis, como a opinião. Eu posso lhe enviar minha cópia.
Babou 25/05
1
@BenCrowell Então, você pode pedir para que minha pergunta sobre física seja eliminada, pois ela estava apenas pedindo essas referências. e espero que alguns comentários sobre eles. Aliás, existe apenas um único artigo.
babou 25/05

Respostas:

6

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.

rrdevido à 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:

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

babou
fonte
A pergunta colocou um argumento específico e perguntou se estava certo. Esta não é uma resposta para a pergunta.
Ben Crowell 25/05
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. Isso faria uma boa pergunta sobre a física.SE, mas não ajuda a responder à pergunta que está sendo feita aqui.
Ben Crowell 25/05
Este site tem muitas perguntas feitas de forma bastante ingênua, e os membros com maior número de representantes tendem a tentar responder de uma maneira pedagógica útil. Sua resposta está apenas denunciando alguém sem representante, que não tem maturidade para fazer uma pergunta com chance de ser significativo. Tentei responder de uma maneira bem motivada e também dar-lhe contexto para que ele pudesse olhar para o trabalho científico real sobre questões semelhantes. Sua resposta diz não: mas você nunca diz por que o infinito deve ser um problema. Não é uma resposta real. O que isso ensina?
Babou 25/05
1
Por que você afirma que tentar determinar se temos um universo infinito disponível é irrelevante para a pergunta?
Babou 25/05
1

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.

vzn
fonte
0

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.

Nikos M.
fonte
0

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!

Jerome
fonte
Isso não significa que, essencialmente, podemos prever que o UTM parará ou ficará sem energia? Como sabemos quanta energia está disponível, podemos apenas simular o UTM e seu consumo de energia até que ele use sua energia disponível e, em seguida, sabemos a resposta sem precisar decidir o problema da parada.
David Richerby
Oh oi David !! Boa tentativa, mas isso infringiria a conservação de energia (erro clássico para não-físicos). A partir do momento em que você definiu A, B e seu "plano", caminhar entre A e B não consome energia, pois esse modelo é adiabático (ou seja, isolado, nada entra ou sai). Mesmo que você suponha que andar consome energia (o que é longe de trivial se você andar em uma superfície plana), essa energia é transferida para outro local do sistema e você poderá recuperá-la com um simples UTM finito. Em outras palavras, seu modelo é E = cste. Não ajuda muito, ajuda?
Jerome
1
A analogia de andar por aí não está me ajudando: estou falando de máquinas de Turing. Suponha que eu tenha uma implementação física de uma máquina de Turing. Como sabemos, não há algoritmo que eu possa usar para determinar se a TM abstrata que ele incorpora terminará em uma determinada entrada. Minha afirmação é que posso simulá-lo no meu PC de mesa para determinar se ele será interrompido por uma entrada específica antes que ela se quebre ou fique sem energia ou o que seja, de modo que o estado da MT física no futuro seja, afinal, um computador função do estado atual. Não vejo como isso viola a conservação de energia.
David Richerby
2
Eu não li tudo isso, mas começa como um comentário em outra resposta. Por favor, não use respostas para iniciar discussões; há bate - papo sobre ciência da computação para isso. (cc @DavidRicherby)
Raphael
Obrigado Raphael. Não tenho créditos suficientes, respondo rapidamente aqui. David, mesmo que seu UTM não diga nada sobre energia, você inclui algumas linhas de código para explicar por que vou parar de andar. Portanto, seu modelo envolve implicitamente uma quantidade Q que "se desgastará" ao longo do caminho. Você assume que Q existe. A Navalha de Occam diz que é arriscado. Especialmente quando você sabe que outra explicação que exige menos suposições parece funcionar. Embora, como eu, você conseguir modelar a caminhada com um UTM, seu código é mais longo do que o meu: para mim a existência de um UTM em si é suficiente para explicar por que eu vou parar de andar
Jerome
0

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.

PyRulez
fonte
-1

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.

Ben Crowell
fonte
Talvez você possa ler minha resposta atualizada (eu ainda estava trabalhando nela) e ser mais explícito e preciso sobre o motivo pelo qual você acha que minha resposta está errada = a parte em que você votou em particular, pois certamente não vejo onde isso poderia ser incompatível com o seu. . Pelo menos o seu ponto de vista técnico pode ser útil para a nossa comunidade, enquanto apenas a redução da votação significa que você considera todas as minhas referências ao trabalho publicado como um absurdo, ou que nossa comunidade não vale mais que desprezo.
babou 25/05
@babou: Um voto negativo não é um ataque pessoal a você ou uma declaração de "desprezo" a esta comunidade. Expliquei o motivo do meu voto negativo. Se você quiser discutir sua resposta, o lugar para fazer isso seria nos comentários da sua resposta, não nos comentários da minha.
Ben Crowell 25/05
Se você acredita no que acabou de escrever em seu comentário, talvez deva ler novamente sua própria "resposta". - - - - - Só para esclarecer as coisas ... Eu nunca voto negativo. Eu comento quando sinto que comentários são necessários.
Babou 25/05
Editei a pergunta para responder à sua resposta (que você também mencionou), porque acho essa resposta insatisfatória. Obrigado por responder, talvez você possa me dizer por que meu UTM não LB imaginado falha?
User2663116
Em uma TM, é apenas a fita que deve ser de tamanho infinito. Uma máquina física de tamanho finito capaz de visitar um número infinito de localizações físicas ("células") seria suficiente, para mostrar "[t] antes que você não consiga construir uma fora de circuitos", você precisa mostrar que isto é impossível. (Talvez isso possa ser discutido com base nos requisitos de energia da máquina, mas você não fazê-lo.)
j_random_hacker