Esta linguagem é decidível?

Question

como diz o título; é essa linguagem decidível e como você prova isso?

$$ l= {\ langle m \ rangle \ mid m \ text {é uma máquina de Turing e há uma entrada que} m \ text}}$$

Answer 1

Sua língua não é decapável. Para mostrar que é suficiente para perceber que a existência de uma máquina de Turing $ t $ que decidiu $ l $ implica a existência de uma máquina de Turing que resolva o problema da parada.

De fato, dada qualquer máquina de Turing $ m $ com entrada $ x $ Você pode construir uma Turing máquina $ m '$ que ignora sua entrada, escreve $ x $ na fita e, em seguida, simula < span class="contêiner matemático"> $ m $ . Claramente $ m '$ pára (independentemente de sua entrada) se e somente se $ m $ detenha na entrada $ x $ . Podemos decidir se $ m '$ detesta verificando se $ m' \ em l $ usando $ t $ com entrada $ m '$ .