# Is undecidability of TMs' properties a statistical statement?

We know (by Rice's theorem) that is it not possible to decide a non-trivial property of a given TM. We could say therefore that we cannot be sure at 100 percent that a given TM has a certain non-trivial property.

Therefore we cannot know if it is 100 percent impossible to show that a given TM has a certain non-trivial property. Right?

So my question is this: as (maybe) we could guess a non-trivial property of a Turing machine, is Rice's theorem just a statistical statement on the probability of finding out a given non-trivial property?

BONUS question: is that probability related to Chaitin's constant?

• No, Rice's theorem is about algorithms that always succeed. It is not about randomized algorithms or about algorithms that work on average. – Yuval Filmus Feb 12 '17 at 16:51
• Yes that's exactly my point. We know nothing about randomized or heuristic methods. Rice's theorem just says this: the probability of finding out a non-trivial property of a given TM with certainty is zero. If in practice we know it's sometimes possible to find out a non-trivial property of a given TM, we can fully turn Rice's theorem into a statistical statement. No? – Jerome Feb 12 '17 at 16:57
• In order to have a statistical statement in this context (in which randomized algorithms don't help) you need a probability distribution on all Turing machines. An enhanced Rice's theorem could say that on instances of length $n$, every algorithm has negligible advantage over constant algorithms. Whether such a theorem holds might depend on your probability distribution. – Yuval Filmus Feb 12 '17 at 17:20