É o languague L={<M>, M aceita uma quantidade finita de palavras} decdidable?

Question

É $L=\{<M> | L(M) \ é \ finito\} $ decidível ?M é um TM.

Eu acho que o seu parente simples de prova para o teorema de rice.Mas eu estou interessado em uma solução que não utilize o Arroz teorema.

Esta minha tentativa :Seja f(<m,w>) ser uma função que funciona da seguinte forma :

1. Executar w em M
2. Se M aceita Construir um TM Mwhich accepts only the word w and return M
3. Se M rejeita Construir um TM Mwhich accepts everything. Return M

Assim, se m é $A_{TM}= \{<M,w>|M \ aceita \ w\}$ sabemos que f(<m,w>) em L.Se m for não, então nós sabemos que f(<m,w>) não aceitar cada palavra e, portanto, infinito de palavras.Assim, f(<m,w>não em L.

É este um mapeamento correto de redução ?

Answer 1

A função definida não é uma redução - ele não pode mesmo parar!

O problema está em execução $m$ no $w$:você pode ter a certeza $m$ não vai ser preso em um loop infinito em $w$?você não pode.

Você pode definir uma adequada redução da seguinte forma:(na entrada $<m,w>$)

Criar a máquina $M_{m,w}$que faz o seguinte algoritmo, e devolver em:(na entrada $s$)

1. Emular $m$ no $w$ para $|s|$ passos.Se $m$ parou, em que momento, rejeitar $s$.Caso contrário, aceite $s$.

Vou deixá-lo para provar que esta é uma boa redução de $H_{TM}$ para $L$ (é um bom exercício!)