Οι μηχανές Turing είναι παρόμοιες με τις μηχανές πεπερασμένων αυτόματα/πεπερασμένων καταστάσεων, αλλά έχουν το πλεονέκτημα της απεριόριστης μνήμης… Είναι ικανές να προσομοιώνουν κοινούς υπολογιστές. ένα πρόβλημα που μπορεί να λύσει ένας κοινός υπολογιστής (δεδομένης αρκετής μνήμης) θα μπορεί επίσης να λυθεί χρησιμοποιώντας μια μηχανή Turing και αντίστροφα.
Ποια είναι η διαφορά μεταξύ RAM και TM;
Μια μηχανή Turing δεν μπορεί Μια μηχανή RAM μπορεί να κάνει αριθμητική σε O(1) (κάτω από ορισμένους περιορισμούς). Μια μηχανή Turing δεν μπορεί. Οι μηχανές Turing προσομοιώνουν πολυωνυμικά μηχανές RAM, δηλαδή, για κάποια σταθερά c, κάθε μηχανή RAM που λειτουργεί σε χρόνο O(nk) μπορεί να προσομοιωθεί από μια μηχανή Turing που λειτουργεί σε χρόνο O(nck).
Είναι η ταινία μιας μηχανής Turing απεριόριστη;
Η μηχανή Turing (TM) είναι μια μηχανή καταστάσεων που αποτελείται από δύο μνήμες: μια απεριόριστη ταινία και έναν πίνακα ελέγχου πεπερασμένης κατάστασης. Η ταινία περιέχει δεδομένα ως σύμβολα. Το μηχάνημα έχει ένα πολύ μικρό σύνολο σωστών λειτουργιών, 6 καθόλου (ανάγνωση, εγγραφή, κίνηση αριστερά, μετακίνηση δεξιά, αλλαγή κατάστασης, στάση) στην κασέτα.
Γιατί η μηχανή Turing είναι ισχυρή;
Πόσο ισχυρές είναι οι μηχανές Turing; Οι μηχανές Turing μπορούν να δεχτούν οποιαδήποτε κανονική γλώσσα ή γλώσσα χωρίς περιεχόμενο. Οι μηχανές Turing μπορούν να εκτελούν βασικούς αριθμητικούς υπολογισμούς … Η διατριβή του Turing δηλώνει ότι οποιοσδήποτε υπολογισμός μπορεί να πραγματοποιηθεί με «μηχανικά μέσα» μπορεί να εκτελεστεί από μια μηχανή Turing (αγνοώντας θέματα απόδοσης).
Μπορούν οι μηχανές Turing να λειτουργούν για πάντα;
turing(turingDescrip) δεν μπορεί ούτε να σταματήσει ούτε να κυκλοφόρησε για πάντα; δεν έχει νόημα σε καμία περίπτωση.
