3 ms·

> I have no idea what isn’t computable. The busy beaver function Σ(n) is not computable, at least, not for every n. If it were, it could be used to determine

by geertj 2y ago

> I have no idea what isn’t computable. The busy beaver function Σ(n) is not computable, at least, not for every n. If it were, it could be used to determine if an arbitrary Turing machine halts, solving the halting problem. To get from this non-computable function to a non-computable number, you can construct the finite number R = 0.Σ(1)Σ(2)Σ(3)... that concatenates all busy beaver numbers. Its first few digits are R = 0.1621 ... (thanks to ChatGPT for this step).

lisper 2y ago
A.K.A.Chatin's constant: https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
hsolatges 2y ago
That is remarkable. Thanks.
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 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 ago
    Exactly! 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 :-)

by geertj 2y ago

lisper 2y ago

A.K.A.Chatin's constant: https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant

hsolatges 2y ago

That is remarkable. Thanks.

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 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 ago
  Exactly! 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 :-)