Zatem jeżeli A działa poprawnie to A(k,k) nie kończy pracy, ponieważ jeżeli A(k,k) kończy pracę, to Ck(k)=A(k,k) nie kończy pracy. Zatem jeżeli A działa poprawnie, to istnieje takie k, że pomimo że Ck(k) nie kończy pracy, A(k,k) nie kończy pracy, zatem A jest niezupełna. Pokazaną metodę diagonalizacji można w ogólności zastosować dla każdej maszyny Turinga z wyrocznią, której konfiguracja może być reprezentowana za pomocą liczby naturalnej.
Maszyna Turinga z wyrocznią a złożoność obliczeniowa
Maszyny Turinga z wyrocznią znalazły zastosowanie w badaniu problemów związanych ze złożonością obliczeniową. Niech AL oznacza zbiór tych języków, które mogą zostać zdefiniowane przy użyciu deterministycznych, należących do klasy A maszyn Turinga z wyrocznią L. Na przykład P3-SAT oznacza zbiór tych języków, w przypadku których przynależność słowa można zdefiniować przy pomocy działającej w czasie wielomianowym deterministycznej maszyny Turinga z wyrocznią rozwiązującą problem 3-SAT.