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".
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.
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.
Articles by others on the same topic
There are currently no matching articles.