Théorème de Rice pour les propriétés non sémantiques

Le théorème de Rice nous dit que les seules propriétés sémantiques des machines de Turing (ie les propriétés de la fonction calculées par la machine) que nous pouvons décider sont les deux propriétés triviales (ie toujours vrai et toujours faux).

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

Existe-t-il un théorème similaire au théorème de Rice qui catégorise la décidabilité de 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 les théorèmes de récurrence / point fixe de Kleene .

computability undecidability Kaveh
la source

Le problème de l’arrêt est essentiellement la question de savoir si l’État qui fait l’arrêt est joignable, de sorte que la question générale de savoir quels États sont joignables sera certainement insoluble.

Carl Mummert

@Carl, oui, je le sais, mais c'est différent de mon exemple. Mon exemple est: étant donné <M>, y a-t-il un état qui est inaccessible (le supprimer n'affectera la machine sur aucune entrée). C'est similaire à une question dans les méthodes formelles: y a-t-il une ligne de code qui n'est pas nécessaire? (ce qui signifie généralement que le programme ne fonctionne pas vraiment comme prévu).

Kaveh

@Kaveh: En général, le problème d'arrêt est équivalent au problème d'arrêt pour les machines qui ignorent complètement leur entrée, et pour cette classe spéciale de machines, le problème d'arrêt '' est '' le problème de savoir si l'état d'arrêt est accessible dans votre sens.

1

$1$

Carl Mummert

@Carl, oui, je connais la réduction directe (nous devons nous assurer que tous les autres états sont accessibles). Mais ma question ne concerne pas le problème lui-même, c'était un exemple facile de langage non sémantique indécidable. Savez-vous donc s'il existe quelque chose de similaire au théorème de Rice qui couvre les propriétés non sémantiques? Ou pensez-vous qu'il est peu probable qu'un tel théorème existe?

Kaveh

Un théorème général qui couvre partiellement l'exemple donné est que toute propriété -hard de la machine sera indécidable. Le problème d'arrêt est réductible au problème d'accessibilité à l'état, ce qui montre que le problème de réductibilité d'état est -hard. $\Sigma^0_1$ $m$ $\Sigma^0_1$

Cependant, ce n'est pas un théorème "si et seulement si" comme le théorème de Rice. Si chaque propriété de l'index de la machine de Turing compte comme une propriété de la machine, alors il n'y aura pas de bonne caractérisation, car il n'y a pas de belle caractérisation dont les réglages sont décidables en termes de index de la réinitialisation. $\Sigma^0_1$

Carl Mummert
la source

Théorème de Rice pour les propriétés non sémantiques

Réponses: