Timeline for Object of proven finiteness, yet with no algorithm discovered?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18 at 7:47 | comment | added | Emil Jeřábek | @C7X Googology is quite unreliable. It is easy to show that this function is not computable; it is essentially the Kolmogorov complexity of $n$ (and it will be called like that in all other sources). See also cstheory.stackexchange.com/a/42375 . | |
| Jul 18 at 4:02 | comment | added | C7X | According to Googology Wiki, there is a sort of inverse of the Busy Beaver function called the Placid Platypus function, whose computability is unknown. This gives a function for which we do not know an algorithm, as opposed to the Busy Beaver function, where we know there can be no algorithm. | |
| Jul 17 at 14:47 | history | edited | Christopher King | CC BY-SA 4.0 |
Unused assumption
|
| Jul 17 at 14:43 | comment | added | LSpice | Re, yes, thanks! I also noticed a minor, more easily resolved, issue in the wording for $F(n)$, which I edited to correct. | |
| Jul 17 at 14:42 | history | edited | LSpice | CC BY-SA 4.0 |
Wording for $F(n)$
|
| Jul 17 at 14:42 | comment | added | JoshuaZ | @LSpice Well that got completely garbled. Hopefully it now makes more sense. | |
| Jul 17 at 14:42 | history | edited | JoshuaZ | CC BY-SA 4.0 |
fix sentence
|
| Jul 17 at 14:40 | history | edited | LSpice | CC BY-SA 4.0 |
Title of survey
|
| Jul 17 at 12:52 | comment | added | JoshuaZ | @HJRW Yeah in these examples, finiteness is trivial. Hence saying at the beginning that this answer is a cheat. Maybe I should have made this a comment and just explicitly asked if they wanted that the finiteness had to be itself non-trivial? | |
| Jul 17 at 12:50 | comment | added | HJRW | In both cases, the proof that the number is finite is trivial, no? I interpret the question as asking for non-trivial proofs of finiteness that are non-constructive in that they don't lead to an algoithm (even a very inefficient one) to output the finite set. Admittedly, the question isn't explicit about this, but it seems to me to be the clear implication of the examples given. | |
| Jul 17 at 11:26 | history | answered | JoshuaZ | CC BY-SA 4.0 |