0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ No, Rice's theorem is about algorithms that always succeed. It is not about randomized algorithms or about algorithms that work on average. $\endgroup$ – Yuval Filmus Feb 12 '17 at 16:51
  • $\begingroup$ 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? $\endgroup$ – Jerome Feb 12 '17 at 16:57
  • 3
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 12 '17 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.