[math-fun] Probability of undecidability
In number theory (as used in Gödel's undecidability proof) what is the probability that a statement is undecidable? Could almost all statements be undecidable? (E.g., look at the fraction of statements of length N that are undecidable, as N -> oo.) --Dan ________________________________________________________________________________________ It goes without saying that .
Your question looks like it's related to "Chaitin's Constant" ( http://en.wikipedia.org/wiki/Chaitin%27s_constant ) the probability that a random Turing machine will halt. Victor On Sat, Jan 7, 2012 at 3:00 PM, Dan Asimov <dasimov@earthlink.net> wrote:
In number theory (as used in Gödel's undecidability proof) what is the probability that a statement is undecidable?
Could almost all statements be undecidable?
(E.g., look at the fraction of statements of length N that are undecidable, as N -> oo.)
--Dan
________________________________________________________________________________________ It goes without saying that .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sat, Jan 7, 2012 at 12:00 PM, Dan Asimov <dasimov@earthlink.net> wrote:
In number theory (as used in Gödel's undecidability proof) what is the probability that a statement is undecidable?
Could almost all statements be undecidable?
Yes, nearly all statements are undecidable (at least, when encoded in a prefix-free form). http://www.sciencedirect.com/science/article/pii/S0196885804001277 -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (3)
-
Dan Asimov -
Mike Stay -
Victor Miller