¿Es imposible saber si dos funciones son equivalentes? Por ejemplo, un escritor compilador quiere determinar si dos funciones que el desarrollador ha escrito realizan la misma operación, ¿qué métodos puede usar para resolver eso? ¿O qué podemos hacer para descubrir que dos TM son idénticas? ¿Hay alguna forma de normalizar las máquinas?

Edición: si el caso general es indecidible, ¿cuánta información necesita tener antes de poder decir correctamente que dos funciones son equivalentes?