Czy nie można wiedzieć, czy dwie funkcje są równoważne? Na przykład autor kompilatora chce ustalić, czy dwie funkcje, które napisał programista, wykonują tę samą operację, jakie metody mogą wykorzystać, aby to określić? A może co możemy zrobić, aby dowiedzieć się, że dwie bazy TM są identyczne? Czy istnieje sposób na normalizację maszyn?

Edytuj: Jeśli ogólny przypadek jest nierozstrzygalny, ile informacji potrzebujesz, aby poprawnie powiedzieć, że dwie funkcje są równoważne?