Αλγοριθμική οικουμενικότητα

Πεπερασμένα αυτόματα (Finite automata)

1. Ι : Τιμές εισόδου
2. Ο : Τιμές εξόδου
3. S : Πεπερασμένο σύνολο εσωτερικών καταστάσεων
4. λ : S X I -> S Συνάρτηση επόμενης κατάστασης
5. δ : S X I -> O Συνάρτηση επόμενης τιμής εξόδου

Η μηχανή του Turing

1. Πεπερασμένο αλφάβητο: Α
2. Πεπερασμένο σύνολο καταστάσεων: Μ
3. Άπειρη ταινία
4. Κεφαλή γραφής και ανάγνωσης
5. Διάγραμμα μετάπτωσης: (Α Χ Μ) -> (Α X {Δ, Α, Σ}) Χ Μ

Παραδείγματα

• Εγγραφή συμβόλου στο τέλος της ταινίας
• Αντιγραφή ταινίας
• Πρόσθεση

Η θέση των Church/Turing

• ΠροηγούμενηΜη υπολογισιμότητα
• Περιεχόμενα
• ΕπόμενηΠιθανοτικοί αλγόριθμοι

 Τελευταία αλλαγή: Δευτέρα, 9 Δεκεμβρίου 1996 11:50 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».