Teorema: è indecidibile.
Dimostrazione: supponiamo per assurdo che sia decidibile, cioè che esiste una macchina di Turing (TM) decisore che decide .
( è una qualsiasi TM)
Consideriamo un’altra decisore che chiamiamo :
- Su input esegue su (riceve la codifica di se stessa come input).
- Se accetta rifiuto, altrimenti accetto.
Ora usiamo la tecnica della diagonalizzazione: consideriamo una matrice infinita che associa ogni possibile TM e la sua codifica al comportamento di in caso riceva in input.

In questa matrice, ovviamente apparirà anche , il cui comportamento è:
e siccome è un decisore, anche lo è.
Questa è una contraddizione, quindi non è riconoscibile.