| ▲ | wasabi991011 5 hours ago |
| I'm not sure what you mean, Graham's number is trivially computable since it is a natural number (finite). Graham's number is not a sequence, so it doesn't matter that the BB sequence grows faster than any computable sequence. |
|
| ▲ | gizmo686 5 hours ago | parent [-] |
| Given a constanct C, you can construct a constant sequence f(n) = C. Since f(n) is trivially computable, we know that BB(n) grows faster than f(n). It follows that there must be some n such that BB(n) > C. |
| |
| ▲ | Someone 5 hours ago | parent | next [-] | | > Given a constanct C, you can construct a constant sequence f(n) = C. > Since f(n) is trivially computable That only is true if C is computable. | | |
| ▲ | wat10000 3 hours ago | parent [-] | | Integers are what's relevant to BB, and all integers are computable. | | |
| ▲ | Scarblac 2 hours ago | parent [-] | | So what if we set C = BB(10)? | | |
| ▲ | wat10000 24 minutes ago | parent | next [-] | | It's hard or maybe impossible to figure out what BB(10) is. But abstractly, it is some finite integer. That finite integer is trivially computable: make a turing machine that hardcodes all the digits and outputs them one by one. You can't know that this machine actually produces BB(10) if you don't know what BB(10) is, but that's separate from the question of whether the number itself is computable. | |
| ▲ | gizmo686 2 hours ago | parent | prev | next [-] | | The integer C is computable. However, we do not know what integer C is without first computing BB(10); and doing that might be not be possible. | |
| ▲ | an hour ago | parent | prev [-] | | [deleted] |
|
|
| |
| ▲ | wasabi991011 3 hours ago | parent | prev [-] | | Ah I see now, thank you. |
|
