théorème de riz pour les propriétés non-sémantiques

Question

riz théorème de nous dire que la seule sémantique de propriétés Turing Machines (les propriétés de la fonction calculée par la machine) que nous pouvons décider sont les deux propriétés triviales (ie toujours vrai et toujours faux ).

Mais il y a d'autres propriétés de machines de Turing qui ne sont pas décidable. Par exemple, la propriété qu'il ya un état inaccessible dans une machine de Turing donnée est indécidable $ ^ {\ dagger} $.

Y at-il un théorème similaire au théorème de Rice qui catégorise la décidabilité des propriétés similaires? Je n'ai pas de définition précise. Tout théorème connu qui couvre l'exemple que j'ai donné serait intéressant pour moi.

$ ^ \ dagger $, il est facile de prouver que cet ensemble est indécidable en utilisant de Kleene point fixe .

Answer 1

Un théorème général qui couvre en partie l'exemple donné est que tout $ \ Sigma ^ $ la propriété -hard 0_1 de la machine sera indécidable. Le problème est $ m arrêt $ -reducible au problème état joignabilité, de sorte que montre le problème de réductibilité d'état est $ \ Sigma ^ -hard $ 0_1.

Cependant, ce n'est pas un « si et seulement si le » théorème comme le théorème de Rice. Si chaque $ \ Sigma ^ propriété $ 0_1 de l'indice des comptes de la machine de Turing comme une propriété de la machine, il ne va pas être une caractérisation agréable, parce qu'il n'y a pas de caractérisation agréable dont R.E. ensembles sont décidables en termes de l'indice de la R.E. ensemble.