Μηχανή Τούρινγκ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Αφαίρεση προτύπου(-ων) επεκτάσεως |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 316:
Θα έπρεπε να προειδοποιήσουμε τον αναγνώστη ότι τέτοια διαγράμματα αναπαριστούν ένα στιγμιότυπο του πίνακά παγωμένο στο χρόνο , ''όχι'' την πορεία ("τροχιά") ενός υπολογισμού ''διαμέσου'' του χρόνου και/ή του χώρου. Αν και κάθε φορά που η μηχανή πολυάσχολος "beaver" θα "τρέχει" , θα ακολουθεί πάντα την ίδια τροχιά-καταστάσεων, αυτό δεν είναι ισχύει και για το "αντίγραφο" της μηχανής το οποίο μπορεί να εφοδιάζεται με ποικίλες εισερχόμενες "παραμέτρους".
Το διάγραμμα "Εξέλιξη του υπολογισμού" δείχνει την εξέλιξη των καταστάσεων (εντολών) του πολυάσχολου "beaver" 3-καταστάσεων διαμέσου του υπολογισμού του από την αρχή στο τέλος. Στο δεξιό μέρος της εικόνας είναι ο Τούρινγκ "πληρης σχηματισμός" (Kleene "κατάσταση", Hopcroft–Ullman "στιγμιαία περιγραφή") σε κάθε βήμα. Αν η μηχανή έπρεπε να διακοπεί και να καθαριστεί και να αδειάσει τόσο το "μητρώο καταστάσεων" όσο και ολόκληρη η ταινία , αυτοί οι "σχηματισμοί" θα μπορούσαν να χρησιμοποιηθούν για να αναζωπυρωθεί ένας υπολογισμός οπουδήποτε στην εξέλιξη του (από Τούρινγκ (1936) ''Undecidable'' pp. 139–140).
==Ισοδύναμα μοντέλα με τη μηχανή Τούρινγκ==
{{Δείτε επίσης|Turing machine equivalents|Register machine|Post–Turing machine}}
Για πολλές μηχανές που θα μπορούσαν να έχουν περισσότερη υπολογιστική ικανότητα από μια απλή γενική μηχανή Τούρινγκ μπορεί να δειχθεί ότι δεν έχουν περισσότερη δύναμη(Hopcroft και Ullman σελ. 159, cf Minsky (1967)). Ίσως υπολογίζουν γρηγορότερα, ή χρησιμοποιούν λιγότερη μνήμη ή το σύνολο εντολών τους είναι μικρότερο, αλλά δεν μπορούν να υπολογίσουν ισχυρότερα( δηλ. περισσότερες μαθηματικές συναρτήσεις). (Θυμηθείτε ότι η [[Church–Turing thesis]] ''υποθέτει'' ότι το παρακάτω είναι πραγματικό για κάθε είδους μηχανή: οτιδήποτε μπορεί να "υπολογιστεί", μπορεί να υπολογιστεί από κάποια μηχανή Τούρινγκ.)
Μια μηχανή Τούρινγκ είναι ισοδύναμη με ένα [[pushdown automaton]] το οποίο έχει δημιουργηθεί πιο ευέλικτο και συνοπτικό χαλαρώνοντας το κριτήριο [[LIFO (computing)|last-in-first-out]] της στοίβας του.
Στο άλλο άκρο, κάποια άλλα απλά μοντέλα μπορούν να αποδειχθούν [[Turing completeness|Turing-equivalent]], δηλ. να έχουν την ίδια υπολογιστική δύναμη όπως το μοντέλο της μηχανής Τούρινγκ.
Κοινά ισοδύναμα μοντέλα είναι τα [[multi-tape Turing machine]], [[multi-track Turing machine]], μηχανές με είσοδο και έξοδο, και το [[Non-deterministic Turing machine|''non-deterministic'' Turing machine]] (NDTM) που αντιτίθεται στην ''ντετερμινιστική'' μηχανή Τούρινγκ(DTM) στην οποία κάθε πίνακας πράξεων έχει το πολύ μια είσοδο για κάθε συνδυασμό από σύμβολα και καταστάσεις.
Οι μηχανές [[Read-only right moving Turing machines|Read-only, right-moving Turing machines]] είναι ισοδύναμες με μη προσδιοριστά πεπερασμένα αυτόματα ([[Nondeterministic finite automaton|NDFAs]]) (καθώς και με προσδιοριτστά πεπερασμένα αυτόματα ([[Deterministic finite automaton|DFAs]]) με μετατροπή χρησιμοποιώντας τον αλγόριθμο [[NDFA to DFA conversion algorithm]]).
Για πρακτικούς και διδακτικούς λόγους η ισοδύναμη [[register machine]] μπορεί να χρησιμοποιηθεί σαν μια συνηθισμένη [[Assembly language|assembly]] [[Γλώσσα προγραμματισμού]].
==Γενικές μηχανές Τούρινγκ==
{{Main|Universal Turing machine}}
[[File:Model of a Turing machine.jpg|thumb|Μια εγαρμογή της μηχανής Τούρινγκ]]
Όπως έγραψε ο Τούρινγκ στο ''Undecidable'', σελ. 128 (με πλάγια γράμματα):
{{quote|Είναι πιθανό να εφευρεθεί μια «απλή μηχανή» η οποία μπορεί να χρησιμοποιηθεί για να υπολογίζει «οποιαδήποτε» υπολογίσιμη ακολουθία. Αν αυτή η μηχανή '''U''' τροφοδοτηθεί με την ταινία, στην αρχή της οποίας γράφεται από κάποια υπολογιστική μηχανή '''M''' η σειρά των πεντάδων διαχωριζόμενες με ερωτηματικά, τότε η '''U''' θα υπολογίσει την ίδια σειρά με την '''M'''.}}
Αυτή η ανακάλυψη θεωρείται πλέον δεδομένη, αλλά στον καιρό του (1936) θεωρήθηκε εκπληκτική. Το μοντέλο του υπολογισμού το οποίο καλεί ο Τούρινγκ «γενική μηχανή» —"'''U'''" για συντομία—, θεωρείται από κάποιους (βλέπε Davis (2000)) ότι είναι η θεμελιώδης θεωρητική επανάσταση, που οδήγησε στη θεωρία του [[stored-program computer]].
{{quote|Η εργασία του Τούρινγκ ... περιέχει, στην ουσία ,την εφεύρεση των σύγχρονων υπολογιστών και μερικών τεχνικών προγραμμάτων που τους συνόδευσαν .|Minsky (1967),σελ. 104}}
Στην έννοια του [[computational complexity]], μια γενική μηχανή Τούρινγκ με πολλαπλή-ταινία χρειάζεται μόνο να είναι πιο αργή από [[Λογάριθμος|λογαριθμικό]] παράγοντα σε σύγκριση με τις μηχανές που προσομοιώνει. Αυτό το αποτέλεσμα μαθεύτηκε το 1966 από τους F. C. Hennie και [[R. E. Stearns]]. (Arora και Barak, 2009, θεώρημα 1.9)
== Αναφορές ==
| |||