Per il example, la lingua delle macchine di Turing che non accettano la propria codifica non può essere accettata da alcuna macchina di Turing.Quali sono tutte le lingue conosciute che le macchine di Turing non possono accettare?
Ci sono infiniti linguaggi che nessuna TM può decidere. Infatti, "la maggior parte" delle lingue è indecidibile; esistono numerabilmente molte lingue decidibili, ma innumerevoli sono le lingue (quindi, innumerevoli e indecidibili).
Il teorema di Rice consente di ottenere molti esempi di lingue che sono indecidibili. Vedi la pagina di Wikipedia: Rice's Theorem
In sostanza, se si dispone di un insieme di lingue non banali (ovvero, esistono TM che riconoscono le lingue nell'insieme e le TM che riconoscono le lingue non nell'insieme), quindi è indecidibile se un linguaggio di una TM arbitraria è in S. Ad esempio, sia S l'insieme formato dalla lingua vuota. Quindi è indecidibile determinare se una TM arbitraria accetta la lingua vuota, cioè senza stringhe. Crea una serie di lingue non banali e hai un nuovo linguaggio indecidibile (tutte le codifiche delle TM che riconoscono le lingue nel set).