O problema que determina sempre que a palavra membro $ \ em $ l (m) decidível ou não?

Question

Dada uma máquina de Turing m no alfabeto {m, e, b, r}, pedimos para determinar se membro $ \ in $ l (m). Você deve perceber que m não é uma máquina específica e pode ser qualquer máquina de Turing com o mesmo alfabeto. Meu objetivo é determinar sempre que esse problema é decidível ou não.

Minha ideia era usar a redução de mapeamento.O objetivo era ver se podemos traduzir todos os problemas da $ a_ {tm} $ que é conhecido por ser indecidível em nosso problema atual.Isso tornaria nosso problema atual indecidível pelo contágio.No entanto, estou lutando em fazê-lo porque não tenho certeza se é possível. $ a_ {tm} $ é definido como uma máquina de Turing M que aceita a palavra w.

Qualquer ajuda para ficar soltada seria apreciada.

Answer 1

Eu tentaria assim:

Redução de $ a_ {tm} $ : dado TM $ a $ und palavra $ W $ .

Use que para definir uma nova máquina $ a '$ que funciona da seguinte forma:

.
1. Execute como $ a $ na entrada $ W $
2. se $ a $ a $ rejeita $ W $ , entrar em loop eterno.
3. se $ a $ aceita, exclua o conteúdo da banda e escreva "membro"