Θεωρία υπολογισμού: Διαφορά μεταξύ των αναθεωρήσεων

Κάποιες από αυτές τις καταστάσεις είναι τελικές, δηλαδή αν η είσοδος εξαντληθεί όσο το αυτόματο είναι σε κάποια από αυτές η συμβολοσειρά είναι αποδεκτή. Υπάρχει ένας πίνακας μεταβάσεων που καθορίζει το σε ποια κατάσταση θα εισέλθει για κάθε περίπτωση.

 

 

Τόσο στα αυτόματα όσο και στις Μηχανές Τούρινγκ υπάρχει μία παραλλαγή τους που διαθέτει ένα πανίσχυρο αλλά αντιρεαλιστικό μαθηματικό χαρακτηριστικό: το μη ντετερμινισμό, τη δυνατότητα δηλαδή σε κάθε βήμα της λειτουργίας τους να μαντεύουν το σωστή διαδρομή που πρέπει να ακολουθήσουν στη συνέχεια από ένα πλήθος δυνατών διαδρομών. Τα μη ντετερμινιστικά αυτόματα συνήθως έχουν εκθετικά λιγότερες καταστάσεις από τα ρεαλιστικά αντίστοιχα ντετερμινιστικά, ενώ οι μη ντετερμινιστικές Μηχανές Τούρινγκ ολοκληρώνουν τη λειτουργία τους σε εκθετικά λιγότερο χρόνο από τις αντίστοιχες ρεαλιστικές ντετερμινιστικές. Ώστόσο κάθε μη ντετερμινιστικό πεπερασμένο αυτόματο μπορεί να μετασχηματιστεί σε ένα ισοδύναμο ντετερμινιστικό που αναγνωρίζει την ίδια γλώσσα (έστω και με πολύ περισσότερες καταστάσεις), καθώς και κάθε μη ντετερμινιστική Μηχανή Τούρινγκ μπορεί να μετασχηματιστεί σε μία ισοδύναμη ντετερμινιστική (έστω και με πολύ μεγαλύτερη χρονική πολυπλοκότητα). Αυτή η ισοδυναμία δεν ισχύει στα αυτόματα στοίβας, αφού υπάρχουν γλώσσες χωρίς συμφραζόμενα που γίνονται αποδεκτές μόνο από μη ντετερμινιστικά αυτόματα στοίβας για τα οποία δεν υπάρχουν αντίστοιχα ντετερμινιστικά. Ειδικά για τις Μηχανές Τούρινγκ έχουν προταθεί και διάφορες άλλες παραλλαγές (πιο ρεαλιστικές, όπως π.χ. με ταινία διπλής κατεύθυνσης ή πολλαπλές κεφαλές ανάγνωσης συμβόλων) οι οποίες όμως έχει αποδειχθεί ότι επίσης είναι ισοδύναμες με την πρότυπη ντετερμινιστική Μηχανή Turing και μάλιστα με την ίδια χρονική πολυπλοκότητα.