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.
Described at: www.sligocki.com/2022/06/10/ctl.html
University of Bristol research group by
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
Specific values of the Busy beaver function by
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
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:
- it is largely recreational mathematics, i.e. done by non-professionals, a bit like the aperiodic tiling. Humbly, they tend to call their results lemmas
- complex structure emerges from simple rules, leading to a complex classification with a few edge cases, much like the classification of finite simple groups
Bibliography:
Automated theorem proving by halting problem reduction by
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
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".
ECDH has smaller keys. youtu.be/gAtBM06xwaw?t=634 mentions some interesting downsides:
- bad curves exist, while in modular, any number seems to work well. TODO why?
- TODO can't find this mentioned anywher else: Diffie-Hellman key exchange has a proof that there is no algorithm, ECDH doesn't. Which proof?
Stopped 2019 apparently. Shame. We need something to be upstreamed!
- source code: github.com/atrosinenko/qemujs
- demo: atrosinenko.github.io/qemujs-demo/
- demo source code: github.com/atrosinenko/qemujs-demo
Conjecture reduction to a halting problem by
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
bbchallenge.org/story#what-is-known-about-bb lists some (all?) cool examples,
- BB(15): Erdős' conjecture on powers of 2, which has some relation to Collatz conjecture
- BB(27): Goldbach's conjecture
- BB(744): Riemann hypothesis
- BB(748): independent from the Zermelo-Fraenkel axioms
- BB(7910): independent from the ZFC
wiki.bbchallenge.org/wiki/Cryptids contains a larger list. In June 2024 it was discovered that BB(6) is hard.
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.
Paper extracted to HTML by Heiner Marxen: turbotm.de/~heiner/BB/mabu90.html
Turing machine that halts if and only if the Goldbach conjecture is false by
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
Turing machine that halts if and only if Collatz conjecture is false by
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
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.
Condensed matter physics course of the University of Oxford by
Ciro Santilli 35 Updated 2025-03-28 +Created 1970-01-01
This could refer to several more specific courses, see the tagged articles for a list.
There are unlisted articles, also show them or only show them.