3 ms·
I see.. You're saying that theoretically, it may be possible to compute the digits of R in a different way, without computing Σ(n). Since it's not possible to u
by geertj 2y ago
I see.. You're saying that theoretically, it may be possible to compute the digits of R in a different way, without computing Σ(n). Since it's not possible to unambiguously get Σ(n) from my definition of R, you cannot use the halting problem to prove that such a computation is impossible.
In your version of R, you can unambiguously get Σ(n) from R, therefore, the halting problem proves that R itself is not computable. Nice!
- thomasahle 2y agoExactly! We must show that computing R will let us compute Σ(n). Not the other way around. Actually, my version has an issue, which is that (while you can read the Σ(n) unambiguously after reading |Σ(n)|) you can't unambiguously get the |Σ(n)| without knowing their length. The most efficient way, I believe, is to just include ||Σ(n)|| as well, and so on recursively down until you have only one digit. But then you'll also need to keep track of the length of the sequence, so it's a mess. Better just write everything in unary. So (1, 4, 6, 13) gets encoded as R = 10 11110 1111110 11111111111110 ... After-all, we are not trying to be efficient with out digits. Just making a theoretical argument :-)