Isso prova que Collatz é um$\Sigma_1$problema?

Question

Então, recebi um e-mail de um dos meus colegas sobre a conjectura de Collatz com um link para o artigo Cientistas da computação tentam encurralar a conjectura de Collatz , de Kevin Hartnett, na Quanta Magazine.

Ao vasculhar a conjectura, parece que nem se sabe que é um$\Pi_1$ou$\Sigma_1$declaração. Veja a questão Math.StackExchange A conjectura de Collatz está em$Σ_1/Π_1$? . Para mais informações, podemos encontrar detalhes na seguinte tese:

• Matthew Alexander Denend, Variantes desafiadoras da conjectura de Collatz , Tese de mestrado, Universidade do Texas em Austin 2018, doi: 10.26153/tsw/1559 .

Isso significa que eles já mostraram que Collatz é um$\Sigma_1$declaração?

Answer 1

Parece que eu estava errado - veja o comentário de Emre Yolcu abaixo.

---

Meu entendimento é que isso não foi realizado (embora o artigo da Quanta seja bastante vago, então eu posso estar interpretando mal a situação).

O artigo Quanta descreve o seguinte processo:

• Crie um sistema de reescrita que sempre termina se Collatz for verdadeiro. Isso foi feito com sucesso - mas observe que o problema de terminação é a priori$\Pi^0_2$, assim como Collatz.

• Tente encontrar uma coleção de matrizes que satisfaça algumas restrições complicadas relacionadas a esse sistema de reescrita. Esta é a tarefa para a qual os solucionadores SAT são relevantes. No entanto, eles ainda não encontraram uma coleção apropriada de matrizes.

• (Foi aqui que eu estava errado:) Mesmo depois de encontrar essa coleção, não terminamos. Tudo o que isso conseguirá é reduzir Collatz a um problema específico sobre multiplicação de matrizes (que o artigo da Quanta não declara - além disso, não explica por que esse problema deve ser mais tratável do que a reescrita ou a conjectura original de Collatz) .

Re: esse terceiro ponto, acho que há uma parte específica do artigo que é potencialmente confusa:

“Você tenta encontrar matrizes que satisfaçam essas restrições”, disse Emre Yolcu, aluno de pós-graduação da Carnegie Mellon que está trabalhando com Heule no problema. “Se você pode encontrá-los, você prova que [eles estão] rescindindo” e, por implicação, você prova Collatz.

Teria sido mais claro escrever "Se você puder encontrá-los, tente provar que [eles estão] rescindindo e, se puder , prove Collatz". Ou seja, encontrar um sistema de matrizes que satisfaça as restrições dadas - o que é de fato$\Sigma^0_1$- é apenas o primeiro passo, e o fato restante que precisamos provar é presumivelmente ainda$\Pi^0_2$.

Na verdade, parece que entendi exatamente errado!

Dito isso, dependendo da elaboração de Emre, podemos ter apenas uma$\Sigma_1$sentença que implica Collatz - não sei se a inexistência de uma família de matrizes apropriada implicaria que Collatz falha.