Est le languague L={<M>, M accepte un nombre fini de mots} decdidable?

Question

Est $L=\{<M> | L(M) \ est \ finis\} $ decidable ?M est un TM.

Je pense que c'est relativement simple, la preuve avec le théorème de rice.Mais je suis intéressé par une solution à ne pas utiliser le théorème de Riz.

Mon essai :Soit f(<m,w>) une fonction qui fonctionne de la façon suivante :

1. Run w M
2. Si M accepte de Construire une TM Mwhich accepts only the word w and return M
3. Si M rejette la Construction d'un TM Mwhich accepts everything. Return M

Donc, si m est dans $A_{TM}= \{<M,w>|M \ accepte \ w\}$ nous savons que f(<m,w>) est dans L.Si m n'est pas dans Une, alors, nous savons que f(<m,w>) accepte tous les mots et, par conséquent, l'infini des mots.Donc f(<m,w>) pas dans L.

Est-ce un bon mappage de réduction ?

Answer 1

La fonction vous avez défini n'est pas une réduction à tous - il peut même pas s'arrêter!

Le problème est en cours d'exécution $m$ sur $w$:pouvez-vous être sûr $m$ ne sera pas bloqué dans une boucle infinie sur $w$?vous ne pouvez pas.

Vous pouvez définir un bon de réduction comme suit:(sur l'entrée $<m,w>$)

Créer la machine $M_{m,w}$que fait l'algorithme suivant, et le retourner à:(sur l'entrée $s$)

1. Émuler $m$ sur $w$ pour $|s|$ les étapes.Si $m$ arrêtée en ce moment, rejeter $s$.Sinon, acceptez $s$.

Je vais le laisser pour vous le prouver, ce qui est un bon de réduction de $H_{TM}$ pour $L$ (c'est un bon exercice!)