Ist es unmöglich zu wissen, ob zwei Funktionen gleichwertig sind? Ein Compiler-Schreiber möchte beispielsweise feststellen, ob zwei vom Entwickler geschriebene Funktionen dieselbe Operation ausführen. Mit welchen Methoden kann er diese herausfinden? Oder können wir mit was herausfinden, dass zwei TMs identisch sind? Gibt es eine Möglichkeit, die Maschinen zu normalisieren?

Bearbeiten: Wenn der allgemeine Fall unentscheidbar ist, wie viele Informationen müssen Sie haben, bevor Sie richtig sagen können, dass zwei Funktionen gleichwertig sind?