[math-fun] probability of undecidability -- are Turing machines especially awesome?
the probability a length-N statement is undecidable practically surely goes to 0 or 1 when N-->infinity... but it depends on the precise language you permit for statements. E.g. if the statement was either an AND of many statements, or an OR of many statements, prob(decidable) would go to 1 and the truth value would almost surely be 0 or 1 respectively. So it is fairly difficult to cook up a language for statements in which this kind of obvious thing does not happen. A related question would be, given a random length-N input for some universal Turing machine, what is the probability it will halt when N-->infinity? In this case, I think the {0,1}-only law is avoided. This suggests that Turing machines actually are pretty special. For a lot of other things like Cellular Automata, tiling, diophantine equations, Kolmogorov optimal-compressedness, etc, I bet the limit probabilities of undecidability ---> 0, but for Turing machines I think it is positive.
On Sat, Jan 7, 2012 at 4:28 PM, Warren Smith <warren.wds@gmail.com> wrote:
A related question would be, given a random length-N input for some universal Turing machine, what is the probability it will halt when N-->infinity? In this case, I think the {0,1}-only law is avoided.
It depends entirely on the universal machine. For example, given a universal machine U, define V such that V(0^100x) = U(x) (that is, if the input starts with a hundred zeros, it takes the rest of the input and feeds it to U) and for all other inputs, it halts if the input is zero mod m and runs forever otherwise. The limiting halting probability is clearly about 1/m. You can design machines that have pretty much any behavior you want. If you stick to prefix-free machines, then the probability goes to zero. This follows immediately from the Kraft inequality. http://en.wikipedia.org/wiki/Kraft's_inequality#Chaitin.27s_constant
This suggests that Turing machines actually are pretty special. For a lot of other things like Cellular Automata, tiling, diophantine equations, Kolmogorov optimal-compressedness, etc, I bet the limit probabilities of undecidability ---> 0, but for Turing machines I think it is positive. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (2)
-
Mike Stay -
Warren Smith