¿Es el idioma L={<M>, M acepta una cantidad finita de palabras} decdidable?

Question

Es $ L = {u003CM> | L (m) is finite } $ decidible?M es una MT.

Creo que es relativamente sencillo demostrarlo con el teorema del arroz.Pero estoy interesado en una solución que no utilice el teorema de Rice.

Este es mi intento:Sea f(<m,w>) una función que funciona de la siguiente manera:

1. Ejecutar w en M
2. Si M acepta Construir una TM Mwhich accepts only the word w and return M
3. Si M rechaza Construir una TM Mwhich accepts everything. Return M

Entonces si m está en $A_{TM}= \{<M,w>|M \ acepta \ w\}$ sabemos que f(<m,w>) está en L.Si m no está en A, entonces sabemos que f(<m,w>) acepta todas las palabras y, por lo tanto, infinitas palabras.Entonces f(<m,w>) no está en L.

¿Es esta una reducción de mapeo correcta?

Answer 1

La función que usted definió no es una reducción en absoluto: ¡puede que ni siquiera se detenga!

El problema esta corriendo $m$ en $w$:¿Puedes estar seguro? $m$ no quedará atrapado en un bucle infinito en $w$?no puedes.

Puede definir una reducción adecuada de la siguiente manera:(en la entrada $<m,w>$)

crear la maquina $M_{m,w}$que hace el siguiente algoritmo y regresa:(en la entrada $s$)

1. Emular $m$ en $w$ para $|s|$ pasos.Si $m$ detenido en ese tiempo, rechazar $s$.De lo contrario, acepta $s$.

Dejaré que usted demuestre que esta es una reducción adecuada de $H_{TM}$ a $l$ (¡es un buen ejercicio!)