Na przykład:
Wyrocznia może zawierać informacje na temat spełnialności dowolnej formuły rachunku zdań w postaci CNF (problem 3-SAT). Ponieważ problem 3-SAT jest NP-zupełny, taka maszyna jest zdolna do rozwiązywania problemów NP w czasie wielomianowym. Wyrocznia może zawierać informacje na temat własności stopu dowolnej maszyny Turinga dla dowolnej danej wejściowej. Taka maszyna jest zdolna do rozwiązywania niektórych problemów algorytmicznie nierozstrzygalnych, np. problemu stopu dla maszyn bez wyroczni i wszelkich problemów algorytmicznie redukujących się do problemu stopu dla maszyn bez wyroczni.
Maszyna Turinga z wyrocznią a problem stopu
Maszyna Turinga z wyrocznią może rozstrzygnąć w skończonej liczbie kroków, czy dowolna maszyna Turinga z określoną daną wejściową nie zakończy pracy. Jednak nie istnieje maszyna Turinga z wyrocznią determinująca w ogólności, które maszyny Turinga z taką samą wyrocznią z określoną daną wejściową nie zakończą pracy. Dowód przyjmuje identyczną formę jak w przypadku standardowych maszyn Turinga. Rozważmy pewną numerację maszyn Turinga z wyrocznią: C1, C2, ... Przypuśćmy, że A jest maszyną Turinga z wyrocznią taką, że jeżeli A zatrzymuje się działając na daną (q,n) to dowodzi, że Cq(n) nie kończy pracy. Dla pewnego k: Ck(n) = A(n,n).