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