Ciro Santilli @cirosantilli  40

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.

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

Bibliography:

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

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.

bbchallenge.org/story#what-is-known-about-bb lists some (all?) cool examples,

wiki.bbchallenge.org/wiki/Cryptids contains a larger list. In June 2024 it was discovered that BB(6) is hard.

Stopped 2019 apparently. Shame. We need something to be upstreamed!

ECDH has smaller keys. youtu.be/gAtBM06xwaw?t=634 mentions some interesting downsides:

If you can reduce a mathematical problem to the Halting problem of a specific turing machine, as in the case of a few machines of the Busy beaver scale, then using Turing machine deciders could serve as a method of automated theorem proving.

That feels like it could be an elegant proof method, as you reduce your problem to one of the most well studied representations that exists: a Turing machine.

However it also appears that certain problems cannot be reduced to a halting problem... OMG life sucks (or is awesome?): Section "Turing machine that halts if and only if Collatz conjecture is false".

The following things come to mind when you look into research in this area, especially the search for BB(5) which was hard but doable:

Bibliography:

Described at: www.sligocki.com/2022/06/10/ctl.html

Bibliography: discuss.bbchallenge.org/t/decider-translated-cyclers/34

Like a cycler, but the cycle starts at an offset.

To see infinity, we check that if the machine only goes left N squares until reaching the repetition, then repetition must only be N squares long.

Bibliography: discuss.bbchallenge.org/t/decider-cyclers/33

Example: bbchallenge.org/279081.

These are very simple, they just check for exact state repetitions, which obviously imply that they will run forever.

Unfortunately, cyclers may need to run through an initial setup phase before reaching the initial cycle point, which is not very elegant.

Also, we have no way of knowing the initial setup length of the actual cycle length, so we just need an arbitrary cutoff value.

And unfortunately, this can lead to misses, e.g. Skelet machine #1, a 5 state machine, has a (translated) cycle that starts at around 50-200M steps, and takes 8 trillion steps to repeat.

They are pioneers in making superconducting magnets, physicist from the university taking obsolete equipment from the uni to his garage and making a startup kind of situation. This was particularly notable for this time and place.

They became a major supplier for magnetic resonance imaging applications.