Ciro Santilli @cirosantilli 35

Turing machine acceleration refers to using high level understanding of specific properties of specific Turing machines to be able to simulate them much fatser than naively running the simulation as usual.

Acceleration allows one to use simulation to find infinite loops that might be very long, and would not be otherwise spotted without acceleration.

This is for example the case of www.sligocki.com/2023/03/13/skelet-1-infinite.html proof of Skelet machine #1.

Best busy beaver machine known since 1989 as of 2023, before a full proof of all 5 state machines had been carried out.

Entry on The Busy Beaver Challenge: bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA

Paper extracted to HTML by Heiner Marxen: turbotm.de/~heiner/BB/mabu90.html

List on The Busy Beaver Challenge: bbchallenge.org/skelet

Bibliography:

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.