Μηχανές Turing (Turing Machines)

Ισχύουν τα παρακάτω

• Κάθε υπολογισμός που μπορεί να εκτελεστεί με μηχανικά μέσα μπορεί να αποδοθεί με μια μηχανή Turing.
• Δεν υπάρχει αλγόριθμος για επιλύσιμο πρόβλημα που δεν μπορεί να απδοθεί από μια μηχανή Turing
• Η μηχανή Turing είναι μια ντετερμινιστική μηχανή
• Μια γλώσσα L λέγεται Αναδρομικά Απαριθμήσιμη Γλώσσα (Recursevily Enumerable) αν υπάρχει μηχανή Turing που την κάνει αποδεκτή. Οι γλώσσες αυτές είναι τύπου 0 σύμφωνα με τον Τσόμσκι.
• Διαθέτει μνήμη και θυμάται μεγάλες σειρές από εισόδους (input)
• Η μνήμη που διαθέτει είναι απεριόριστη

Τυπικός ορισμός

Μια μηχανή Turing ορίζεται ως μία πλειάδα επτά (7) στοιχείων: P = (K, Σ, s, F, δ, Γ, b) όπου:

• K (ή Q) είναι ένα πεπερασμένο σύνολο καταστάσεων
• Σ είναι ένα αλφάβητο (πεπερασμένο σύνολο συμβόλων)
• s ή (q₀) ∈ K είναι η αρχική κατάσταση
• F ⊆ K είναι το σύνολο των τελικών καταστάσεων. Έχουμε καταστάσεις αποδοχής (accept states) και καταστάσεις απόρριψης (reject states).
• δ είναι μια σχέση μετάβασης (ΚxΣ → ΚxΓx(R|L))
• Γ είναι ένα πεπερασμένο σύνολο συμβόλων ταινίας
• b είναι το κενό σύμβολο b ∉ Σ

Μια σχέση μετάβασης μπορεί να έχει την εξής μορφή: δ(q0, a) → (q1, y, R) όπου:

• q0, q1 καταστάσεις από το σύνολο Κ (ή Q)
• a σύμβολο από το αλφάβητο Σ
• y σύμβολο από το αλφάβητο Γ
• R Right (μετακίνηση δεξιά ή αριστερά αν έχουμε L)