33
$\begingroup$

Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always true and always false).

But there are other properties of Turing Machines that are not decidable. For example, the property that there is an unreachable state in a given Turing machine is undecidable$^{\dagger}$.

Is there a similar theorem to Rice's theorem that categorizes the decidability of similar properties? I don't have a precise definition. Any known theorem that covers the example I have given would be interesting for me.

$^\dagger$ it is easy to prove that this set is undecidable using Kleene's Recursion/Fixed Point theorems.

Improve this question
$\endgroup$
4
  • $\begingroup$ The halting problem is essentially the question whether the halting state is reachable, so the general question of which states are reachable is certainly going to be unsolvable. $\endgroup$
    – Carl Mummert
    Commented Mar 6, 2012 at 23:16
  • $\begingroup$ @Carl, yes, I know that, but that is different from my example. My example is: given <M>, is there a state which is unreachable (removing it will not effect the machine on any input). It is similar to a questions in Formal Methods: is there a line of code that is unnecessary? (which usually means that the program is not really working as expected). $\endgroup$
    – Kaveh
    Commented Mar 6, 2012 at 23:18
  • $\begingroup$ @Kaveh: In general the halting problem is $1$-equivalent to the halting problem for machines that completely ignore their input, and for that special class of machines the halting problem ''is'' the problem of whether the halting state is reachable in your sense. $\endgroup$
    – Carl Mummert
    Commented Mar 6, 2012 at 23:24
  • $\begingroup$ @Carl, yes, I know the direct reduction (we have to make sure that all other states are reachable). But my question is not about the problem itself, it was an easy example of undecidable non-semantic language. So do you know if there is anything similar to Rice's theorem that covers non-semantic properties? Or do you think that it is unlikely that such a theorem exists? $\endgroup$
    – Kaveh
    Commented Mar 6, 2012 at 23:29

1 Answer 1

Reset to default
16
$\begingroup$

A general theorem that partially covers the example given is that any $\Sigma^0_1$-hard property of the machine will be undecidable. The halting problem is $m$-reducible to the state-reachability problem, so that shows the state reducibility problem is $\Sigma^0_1$-hard.

However, this is not an "if and only if" theorem like Rice's theorem. If every $\Sigma^0_1$ property of the index of the Turing machine counts as a property of the machine, then there is not going to be a nice characterization, because there is not any nice characterization of which r.e. sets are decidable in terms of the index of the r.e. set.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.