3 ms·
>Like what? The halting problem is (I think?) the standard example. Here's a short video on it https://youtu.be/macM_MtS_w4 https://youtu.be/macM_MtS_w4
by gammalost 5y ago
>Like what?
The halting problem is (I think?) the standard example.
Here's a short video on it https://youtu.be/macM_MtS_w4 https://youtu.be/macM_MtS_w4
- anyfoo 5y agoChaitin's constant is closely tied to the halting problem: Each bit essentially tells you if a program (in the particular order the programs are listed in the constant) halts or not. Computing every bit in there would mean knowing for every program if it halts or not, which would solve the halting problem, which we can prove is impossible. So we cannot compute that constant.