Można pokazać, że dany problem jest rozstrzygalny na niedeterministycznej maszynie Turinga wtedy i tylko wtedy, gdy jest rozstrzygalny na deterministycznej maszynie Turinga.
Każdy problem rozstrzygalny na deterministycznej maszynie Turinga jest rozstrzygalny na niedeterministycznej maszynie Turinga. Jest to oczywiste, jako że deterministyczną maszynę Turinga można traktować jako szczególny przypadek niedeterministycznej maszyny Turinga.
Każdy problem rozstrzygalny na niedeterministycznej maszynie Turinga jest rozstrzygalny na deterministycznej maszynie Turinga. Idea dowodu polega na pokazaniu, że dysponując algorytmem niedeterministycznym rozstrzygającym dany problem, można skonstruować algorytm deterministyczny poprzez przeszukiwanie wszerz drzewa obliczeń algorytmu niedeterministycznego.
Realizacja fizyczna W przeciwieństwie do maszyn Turinga w modelu podstawowym, maszynom niedeterministycznym nie odpowiada działanie jakiegokolwiek klasycznego urządzenia (z dokładnością do przejść pomiędzy zbiorami stanów).