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.