Ciro Santilli @cirosantilli 37

mathoverflow.net/questions/309044/is-there-a-known-turing-machine-which-halts-if-and-only-if-the-collatz-conjectur suggests one does not exist. Amazing.

Intuitively we see that the situation is fundamentally different from the Turing machine that halts if and only if the Goldbach conjecture is false because for Collatz the counter example must go off into infinity, while in Goldbach conjecture we can finitely check any failures.

Amazing.

This could refer to several more specific courses, see the tagged articles for a list.

On The Busy Beaver Challenge: bbchallenge.org/68329601

Non formal proof with a program March 2023: www.sligocki.com/2023/03/13/skelet-1-infinite.html Awesome article that describes the proof procedure.

Formal proof August 2023: discuss.bbchallenge.org/t/skelet-1-is-a-translated-cycler-coq-agrees/166

The proof uses Turing machine acceleration to show that Skelet machine #1 is a Translated cycler Turing machine with humongous cycle paramters:

Once you hear about the uncomputability of such problems, it makes you see that all Diophantine equation questions risk being undecidable, though in some simpler cases we manage to come up with answers. The feeling is similar to watching people trying to solve the Halting problem, e.g. in the effort to determine BB(5).

The set of all algebraic numbers forms a field.

This field contains all of the rational numbers, but it is a quadratically closed field.

Like the rationals, this field also has the same cardinality as the natural numbers, because we can specify and enumerate each of its members by a fixed number of integers from the polynomial equation that defines them. So it is a bit like the rationals, but we use potentially arbitrary numbers of integers to specify each number (polynomial coefficients + index of which root we are talking about) instead of just always two as for the rationals.

Each algebraic number also has a degree associated to it, i.e. the degree of the polynomial used to define it.

TODO understand.

mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/103415#103415 provides a specific single undecidable Diophantine equation.

Polynomial time for most inputs, but not for some very rare ones. TODO can they be determined?

But it is better in practice than the AKS primality test, which is always polynomial time.