É impossível saber se duas funções são equivalentes? Por exemplo, um compilador quer determinar se duas funções que o desenvolvedor escreveu executam a mesma operação, que métodos ele pode usar para descobrir isso? Ou o que podemos fazer para descobrir que duas TMs são idênticas? Existe uma maneira de normalizar as máquinas?

Edit: Se o caso geral é indecidível, quanta informação você precisa ter antes de poder dizer corretamente que duas funções são equivalentes?