OurBigBook.com $£ Sponsor 中国独裁统治 China Dictatorship 新疆改造中心、六四事件、法轮功、郝海东、709大抓捕、2015巴拿马文件邓家贵、低端人口、西藏骚乱

Conjecture reduction to a halting problem

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.

Table of contents 71 2
- Turing machine that halts if and only if the Goldbach conjecture is false (27-state) Conjecture reduction to a halting problem
- Turing machine that halts if and only if Collatz conjecture is false Conjecture reduction to a halting problem 39

 Ancestors (12)

 Incoming links (2)