6 ms·
I think ChatGPT got it a little wrong. For the argument to work, you need to be able to reconstruct the Σ function from R. But you don't know the boundaries of
by thomasahle 2y ago
I think ChatGPT got it a little wrong.
For the argument to work, you need to be able to reconstruct the Σ function from R. But you don't know the boundaries of the numbers, so you can't.
However, if you include the number of digits in each number, that is
R = 0.|Σ(1)|Σ(1) |Σ(2)|Σ(2) |Σ(3)|Σ(3)... = 0.11 14 16 213
That should work.
- deleted 2y ago[deleted]
- geertj 2y agoI 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 :-)