Ciò dimostra che Collatz è a $\Sigma_1$problema?
Così ho ricevuto un'e-mail da uno dei miei colleghi sulla Congettura di Collatz con un collegamento all'articolo Gli scienziati informatici tentano di mettere all'angolo la Congettura di Collatz di Kevin Hartnett su Quanta Magazine.
Scavando attraverso la congettura, sembra che non sia nemmeno noto che sia a$\Pi_1$o$\Sigma_1$dichiarazione. Vedi la domanda Math.StackExchange È la congettura di Collatz in$Σ_1/Π_1$? . Per ulteriori informazioni possiamo trovare dettagli nella seguente tesi:
- Matthew Alexander Denend, Varianti sfidanti della congettura di Collatz , tesi di laurea, The University of Texas at Austin 2018, doi: 10.26153/tsw/1559 .
Significa che hanno già dimostrato che Collatz è un$\Sigma_1$dichiarazione?
Risposte
Sembra che mi sbagliassi - vedi il commento di Emre Yolcu qui sotto.
La mia comprensione è che ciò non è stato realizzato (sebbene l'articolo di Quanta sia piuttosto vago, quindi potrei fraintendere la situazione).
L'articolo di Quanta descrive il seguente processo:
Crea un sistema di riscrittura che termina sempre se Collatz è vero. Ciò è stato eseguito con successo, ma si noti che il problema di terminazione è a priori$\Pi^0_2$, proprio come Collatz.
Prova a trovare una raccolta di matrici che soddisfino alcuni complicati vincoli relativi a quel sistema di riscrittura. Questo è il compito per cui i solutori SAT sono rilevanti. Tuttavia, non hanno ancora trovato una raccolta appropriata di matrici.
(Questo è dove mi sbagliavo:)
Anche dopo aver trovato una tale raccolta, non abbiamo finito. Tutto ciò che ciò otterrà è ridurre Collatz a un problema particolare sulla moltiplicazione di matrici (che l'articolo di Quanta non afferma - inoltre, non spiega perché quel problema dovrebbe essere più trattabile di quello di riscrittura o della congettura di Collatz originale) .
Re: quel terzo punto elenco, penso che ci sia una parte particolare dell'articolo che potrebbe confondere:
"Cerchi di trovare matrici che soddisfino questi vincoli", ha affermato Emre Yolcu, uno studente laureato alla Carnegie Mellon che sta lavorando con Heule sul problema. "Se riesci a trovarli, dimostri che stanno finendo" e, implicitamente, dimostri Collatz.
Sarebbe stato più chiaro scrivere "Se riesci a trovarli, allora provi a dimostrare che [stanno] finendo, e se riesci a provare Collatz". Cioè, trovare un sistema di matrici che soddisfi i vincoli dati - il che è effettivamente$\Sigma^0_1$- è solo il primo passo, e il fatto rimanente che dobbiamo dimostrare è presumibilmente ancora$\Pi^0_2$.
In realtà mi sembra di aver capito esattamente male!
Detto questo, in attesa di ulteriori elaborazioni da parte di Emre, potremmo avere solo a$\Sigma_1$frase che implica Collatz - Non so se la non esistenza di una famiglia di matrice appropriata implicherebbe che Collatz fallisca.