Ciro Santilli $$ Sponsor Ciro $$ 中国独裁统治 China Dictatorship 新疆改造中心、六四事件、法轮功、郝海东、709大抓捕、2015巴拿马文件 邓家贵、低端人口、西藏骚乱
🔗
🔗
🔗
is the largest number of 1's written by a halting -state Turing machine.
🔗
Some variant definitions define it as the number of time steps taken by the machine instead. Wikipedia talks about their relationship, but no patience right now.
🔗
🔗
This problem is theoretically interesting because many important mathematical conjectures have been proved to be equivalent to whether a given Turing machine halts or not, this is notably the case for:
🔗
Therefore, if we were able to compute , we would be able to prove those conjectures automatically, by letting the machine run up to , and if it hadn't halted by then, we would know that it would never halt.
🔗
Of course, in practice, is generally uncomputable, so we will never know it. And furthermore, even if it were, it would take a lot longer than the age of the universe to compute any of it, so it would be useless.
🔗
However, philosophically speaking at least, the number of states of the equivalent Turing machine gives us a philosophical idea of the complexity of the problem.
🔗
🔗

Ancestors