Timeline for Computationally challenging integer sequences
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 26, 2023 at 2:54 | comment | added | Sidharth Ghoshal | $BB(n) \mod K$ or $\text{rad}(BB(n))$ or any other function that can compress the numbers a fair bit would also be extremely difficult to compute but not exploding in size. I don’t know if such numbers would be uncomputable necessarily. | |
| Aug 7, 2022 at 10:32 | comment | added | M. Winter | Is this really a computational problem? No fixed algorithm can tell you whether a particular Turing machine runs forever. Simulating the TM only works if it eventually holds. And if you need a new idea for every n then this qualifies more as a theoretical problem rather than a computational one, doesn't it? | |
| Mar 22, 2017 at 17:23 | comment | added | cody | It is possible, however, for the value of $\mathrm{BB}(10)$, to be undecidable in $ZFC$, meaning that the statement $\mathrm{BB}(10)=k$ cannot be proven in $ZFC$ for any concrete $k$. Currently we know that $\mathrm{BB}(8000)$ has this property (arxiv.org/pdf/1605.04343) but the number has been reduced dramatically in subsequent efforts (to around 2000 if memory serves). | |
| Mar 8, 2017 at 22:53 | comment | added | Aryeh Kontorovich | Ok, but then the correct terminology is provable. Any singleton set (consisting of a number or a string) is computable. So is any finite set for that matter. | |
| Mar 8, 2017 at 19:50 | comment | added | aorq | @AryehKontorovich: It means that you can't prove that BB(n) is what it is. | |
| Mar 8, 2017 at 10:58 | comment | added | Aryeh Kontorovich | What does it mean for a given BB number to be uncomputable -- it's just a number! What's uncomputable is the function $f(n)$ which returns the $n$th BB number. | |
| Mar 6, 2017 at 6:00 | review | First posts | |||
| Mar 6, 2017 at 6:17 | |||||
| Mar 6, 2017 at 5:59 | history | answered | none | CC BY-SA 3.0 |