Para example, el lenguaje de las máquinas de Turing que no aceptan su propia codificación no puede ser aceptado por ninguna máquina de Turing.¿Cuáles son todos los idiomas conocidos que las máquinas de Turing no pueden aceptar?
Hay infinitos idiomas que ninguna TM puede decidir. De hecho, "la mayoría de los idiomas" son indecidibles; hay muchos lenguajes decidibles, pero innumerables idiomas (por lo tanto, incontables muchos indecidibles).
El teorema de Rice le permite encontrar muchos ejemplos de idiomas que son indecidibles. Ver la página de Wikipedia: Rice's Theorem
Básicamente, si tiene un conjunto de idiomas que no es trivial (es decir, hay TM que reconocen idiomas en el conjunto y TM que reconocen idiomas que no están en el conjunto), entonces es indecidible si un lenguaje arbitrario de TM está en S. Por ejemplo, que S sea el conjunto que consiste en el idioma vacío. Entonces es indecidible determinar si una MT arbitraria acepta el lenguaje vacío, es decir, sin cadenas. Propón un conjunto de idiomas no triviales, y tienes un nuevo lenguaje indecidible (todas las codificaciones de TM reconocen los idiomas en el conjunto).