.
Στη θεωρία πολυπλοκότητας και στη θεωρία υπολογισιμότητας, μια μηχανή χρησμού είναι μια αφηρημένη μηχανή που χρησιμοποιείται για τη μελέτη προβλημάτων απόφασης. Μπορεί να απεικονιστεί ως μια μηχανή Turing με ένα μαύρο κουτί, που ονομάζεται μαντείο, το οποίο είναι σε θέση να λύσει ορισμένα προβλήματα σε μία μόνο λειτουργία. Το πρόβλημα μπορεί να είναι οποιασδήποτε κατηγορίας πολυπλοκότητας. Ακόμη και προβλήματα που δεν μπορούν να επιλυθούν, όπως το πρόβλημα διακοπής, μπορούν να χρησιμοποιηθούν.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
