Wykazanie tego faktu jest trudne i było zasadniczą częścią dowodu równoważności dziesiątego problemu Hilberta i problemu stopu.

Warto zauważyć, że jeśli dane równanie diofantyczne ma rozwiązanie i co równoważne odpowiadająca mu maszyna Turinga kończy pracę, to fakt ten zawsze można stwierdzić algorytmicznie, np. poprzez jawne pokazanie skończonej listy kroków, w której dana maszyna osiąga instrukcje stop. Jeśli jednak odpowiedź brzmi „nie”, to nie można tego stwierdzić w oparciu o jakikolwiek skończony zbiór reguł, który da się zredukować do postaci maszyny Turinga. Można podać różne zbiory reguł pozwalające w niektórych przypadkach dowieść, że rozwiązanie nie istnieje (jak np. pokazany wyżej dowód opierający się na parzystości zmiennych), ale taki zbiór nigdy nie będzie wystarczający do uwzględnienia wszystkich przypadków równań, które nie posiadają rozwiązania w dziedzinie liczb całkowitych. Co więcej fakt, że dana maszyna Turinga jest skuteczna w odniesieniu do pewnego podzbioru równań, pociąga prawdziwość nowego twierdzenia o nierozwiązywalności innego równania, którego jednak już ta maszyna nie rozstrzyga.