Questa lingua è decidabile?

Question

Come dice il titolo; Questa lingua è decidabile e come lo dimostri?

$$ l={\ Langle m \ Rangle \ MID M \ Text {è una macchina di Turing e c'è un ingresso che} m \ Text {fermini su}}}$$

Answer 1

La tua lingua non è decidabile. Per dimostrare che è sufficiente notare che l'esistenza di una macchina di Turing $ T $ che ha deciso $ l implica l'esistenza di una macchina di Turing che risolve il problema di fermezza.

Infatti, dato qualsiasi macchina di tentazione $ m $ con ingresso $ x $ È possibile costruire un Turing macchina $ M '$ che ignora il suo ingresso, scrive $ x $ sul nastro, quindi simula < Span Class="Math-Container"> $ m $ . Chiaramente $ M '$ si ferma (indipendentemente dal suo ingresso) se e solo se $ m $ si ferma in ingresso $ x $ . Possiamo decidere se $ M '$ si ferma controllando se $ m' \ in l $ usando $ T $ con ingresso $ m '$ .