3 ms·
I believe that Chaitin’s constant Ω could be approximated, possibly to the point where it could be "computed". It's impossible to emulate a Turing machine, but
by mikewarot 5y ago
I believe that Chaitin’s constant Ω could be approximated, possibly to the point where it could be "computed".
It's impossible to emulate a Turing machine, but you can emulate a Turing machine limited to N states. Make A runs of B random bits in said pseudo-Turing(N) machine, observe distribution of programs that halt, or exceed N. Increase A, B or N, and see if some obvious asymptotes arise as you chart the results.
- lisper 5y agoYes, you can do this, but it isn't very interesting because the number you get depends on the details of the computational model that you use to specify the computation (because that's how you define the probability distribution). But people have gone through the exercise, e.g.: https://www.researchgate.net/publication/267327970_Empirical_Estimation_of_the_Halting_Probabilities https://www.researchgate.net/publication/267327970_Empirical...
- drdeca 5y agoIt is [not computable] in the sense that [there is no program which, given an input n, outputs the first n digits, and then halts]. However, the set of rational numbers less than it, is computationally enumerable, in the sense that there is a program which produces an endless non decreasing sequence of rational numbers which will eventually exceed any rational number less than it. You say “using N states”. This could work, but I think the standard approach is to instead just say to run all programs in a dovetail fashion, and repeatedly count, say, which of the first n programs have halted within n timesteps (and compute the lower bound that that implies on the constant)