VERDADEIRO, MAS IMPOSSÍVEL DE PROVAR
Imagine uma multidão de vizinhos, cada par com sua própria exigência. Se todas as exigências puderem ser atendidas ao mesmo tempo, todos ficam satisfeitos. Se duas exigências entram em conflito, alguém precisa ceder. Os físicos que estudam ímãs feitos de spins quânticos enfrentam exatamente essa questão. Cada par de spins vizinhos tem uma regra de energia, e o sistema tenta atingir sua energia mais baixa. Quando um único estado consegue satisfazer todos os pares ao mesmo tempo, o modelo é chamado de livre de frustração (frustration-free).
Esses modelos são muito valorizados. Entre os exemplos famosos estão o modelo AKLT e o código tórico de Kitaev, pontos de referência para fases exóticas da matéria. Ser livre de frustração também impõe limites fortes ao modo como um material pode se comportar em baixa energia. Daí surge uma pergunta natural: dadas as regras para um par, o modelo é livre de frustração em redes de todos os tamanhos?
Naoto Shiraishi, da Universidade de Tóquio, estudou essa questão numa grade quadrada de spins, com a mesma regra repetida entre cada par de vizinhos. Cada spin pode assumir d estados diferentes. A resposta vem em duas partes que parecem se contradizer.
Uma rede basta
Para um único tamanho de rede, a questão é álgebra linear comum. O problema é a infinidade de tamanhos. Verificar grades cada vez maiores pode revelar uma falha, mas nunca prova o sucesso para todas elas.
O primeiro teorema elimina esse infinito. Para cada valor de d, existe um tamanho-limite finito, o mesmo para todas as regras possíveis. Se um modelo é livre de frustração numa grade desse tamanho, ele é livre de frustração em todas. Portanto, o problema é decidível: existe um algoritmo que sempre responde sim ou não.
A chave é um clássico da álgebra, o teorema da base de Hilbert. A condição em cada tamanho pode ser escrita como um conjunto de equações polinomiais, sempre nas mesmas 2d⁴ incógnitas — as entradas das duas matrizes da regra. O teorema garante que uma lista infinita dessas equações tem as mesmas soluções que alguma parte finita dela. Como uma grade livre de frustração continua livre de frustração em qualquer grade menor recortada dela, um único tamanho então basta.
Não é um resultado trivial. Exatamente no mesmo tipo de modelo, uma questão relacionada — se existe um gap de energia acima do estado mais baixo — foi demonstrada indecidível, mesmo para um d fixo.
Um conjunto de ladrilhos que caça contradições
O segundo teorema vai no sentido oposto. Supondo que os axiomas padrão da matemática, conhecidos como ZFC, não contenham nenhuma contradição, existe um modelo livre de frustração cuja ausência de frustração não pode ser provada a partir desses axiomas.
A construção usa ladrilhos de Wang (Wang tiles): quadrados com bordas coloridas, assentados sem rotação, em que os vizinhos precisam combinar. Para qualquer programa de computador, é possível projetar um conjunto finito de ladrilhos capaz de cobrir todo o plano infinito se e somente se o programa rodar para sempre. Cada ladrilho se torna um estado de um spin. Cada par proibido de ladrilhos vizinhos custa uma unidade de energia. O modelo é livre de frustração exatamente quando os ladrilhos conseguem cobrir o plano.
Agora escolha o programa que vasculha todas as provas possíveis em busca de uma contradição na ZFC e para se encontrar uma. Se a ZFC for consistente, o programa nunca para, e o modelo é livre de frustração. Mas se a ZFC pudesse provar isso, ela provaria a própria consistência — o que o segundo teorema da incompletude de Gödel proíbe.
O modelo é explícito, embora complicado demais para ser escrito por extenso. Suas regras nem sequer são verdadeiramente quânticas: os termos de energia comutam todos entre si, como simples restrições clássicas.
Um tamanho-limite que existe, mas não pode ser nomeado
Como um problema pode ser decidível e ainda assim conter uma afirmação que não pode ser provada? A resposta está no tamanho-limite. Ele é finito para todo d, mas nenhum algoritmo consegue calculá-lo a partir de d. Para a dimensão do modelo indemonstrável, os axiomas provam que existe um tamanho-limite finito — mas não conseguem provar que algum número em particular o seja.
O tamanho-limite também cresce de forma absurdamente rápida: pelo menos tão rápido quanto a função castor atarefado (busy beaver) — o maior número de marcas que um programa que para, com um dado número de estados, pode deixar em sua fita —, que supera toda função que um computador consegue calcular. Seu valor para máquinas de cinco estados só foi determinado em 2024, segundo o artigo; o valor para seis estados ainda é desconhecido.
A distância entre existir e saber
A decidibilidade exige apenas que exista um algoritmo correto, não que alguém consiga construí-lo. Na maioria dos casos familiares, a diferença não importa. Aqui, argumenta Shiraishi, ela se torna a história toda — e aparece num problema comum de física, numa simples grade quadrada. Shiraishi declara que o ChatGPT foi usado para estabelecer o resultado de decidibilidade e para esclarecer como ele se articula com o resultado de indemonstrabilidade. Determinar os tamanhos-limite reais, mesmo para spins muito pequenos, fica como um desafio em aberto.
