3 ms·

A related thing that occurred to me the other day: there's some number in [0, 1] that encodes every state of every possible Turing machine (the number of Turing

A related thing that occurred to me the other day: there's some number in [0, 1] that encodes every state of every possible Turing machine (the number of Turing machines is countable, the duration of its run is countable, and the states at each step are countable, so you can diagonalize that and make a real number out of it). I'm pretty sure you can take that further and show that all possible mathematical proofs, including the Godel unsolvable ones (I think...they're just proofs that are infinitely long but countably so), can also be encoded in a single real number. That makes it feel like the reals are pretty big.

Rinum 5y ago
I think you'll like this - https://youtu.be/HeQX2HjkcNo https://youtu.be/HeQX2HjkcNo
ttctciyf 5y ago
This sounds a little like Chaitin's constant Omega (Ω), which is very roughly a number in [0, 1] which is the probability that a randomly chosen program (for a universal Turing machine, U) will halt. This has the interesting property that knowing the first n bits of Ω allows you to determine whether any program (for U) of length up to n will halt, in other words you could solve the halting problem for programs of length up to n. As Wikipedia puts it: > Because many outstanding problems in number theory, such as Goldbach's conjecture, are equivalent to solving the halting problem for special programs (which would basically search for counter-examples and halt if one is found), knowing enough bits of Chaitin's constant would also imply knowing the answer to these problems. But as the halting problem is not generally solvable, and therefore calculating any but the first few bits of Chaitin's constant is not possible, this just reduces hard problems to impossible ones, much like trying to build an oracle machine for the halting problem would be. - https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant

Rinum 5y ago

I think you'll like this - https://youtu.be/HeQX2HjkcNo https://youtu.be/HeQX2HjkcNo

ttctciyf 5y ago

This sounds a little like Chaitin's constant Omega (Ω), which is very roughly a number in [0, 1] which is the probability that a randomly chosen program (for a universal Turing machine, U) will halt. This has the interesting property that knowing the first n bits of Ω allows you to determine whether any program (for U) of length up to n will halt, in other words you could solve the halting problem for programs of length up to n. As Wikipedia puts it: > Because many outstanding problems in number theory, such as Goldbach's conjecture, are equivalent to solving the halting problem for special programs (which would basically search for counter-examples and halt if one is found), knowing enough bits of Chaitin's constant would also imply knowing the answer to these problems. But as the halting problem is not generally solvable, and therefore calculating any but the first few bits of Chaitin's constant is not possible, this just reduces hard problems to impossible ones, much like trying to build an oracle machine for the halting problem would be. - https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant