Δείτε εδώ τα πιο πρόσφατα μηνύματα από όλες τις περιοχές συζητήσεων, καθώς και όλες τις υπηρεσίες της AcroBase. H εγγραφή σας είναι γρήγορη και εύκολη. |
|
Κεντρική σελίδα |
Λίστα Μελών | Games | Σημειώστε όλα τα forums ως διαβασμένα | Σημειώστε όλα τα forums ως διαβασμένα |
|
|
Εργαλεία Θεμάτων | Τρόποι εμφάνισης |
#1
|
#2
|
|
||||
Universal Turing Machine είναι μια μηχανή Turing ικανή να εκτελέσει οποιαδήποτε άλλη μηχανή Turing με κατάλληλη υλοποίηση.
Προφανώς λόγω της χρήστης του «οποιαδήποτε», η απόδειξή σου πρέπει να είναι απαγωγή εις άτοπο της θέσης ότι υπάρχει μηχανή Turing που η υποτιθέμενα Universal μηχανή σου δε μπορεί να εκτελέσει. Αυτό κάνει πολλές τέτοιες αποδείξεις εξαιρετικά δύσκολες (αν όχι αδύνατες). Ομολογουμένως δε θυμάμαι τώρα πώς κάναμε τις αποδείξεις για περιπτώσεις UTM, αλλά οι περισσότερες αποδείξεις με μηχανές Turing βγαίνουν απαγωγικά: παίρνεις τη μηχανή Turing σου και αποδεικνύεις ότι με κατάλληλα τεχνάσματα, η μηχανή αυτή είναι ισοδύναμη σε δυνατότητες με μια συμβατική μηχανή Turing. Αυτό το δείχνεις κατασκευάζοντας μια μηχανή Turing που εμπεριέχει τις δυνατότητες της άλλης μηχανής. Σε μπέρδεψα περισσότερο τώρα, έτσι;
__________________
www.bedroomlan.org |
#3
|
|
||||
τι εννοεις "οποιαδηποτε αλλη μηχανη"; Οταν λεμε "μηχανη Τουρινγκ" ενα πραγμα δεν εννοουμε;
(αυτη με την απειρη λωριδα)
__________________
Υπάρχουν σε όλα δύο απόψεις... Αυτή που λέω εγώ, και η σωστή! |
#4
|
|
||||
Όλες οι γνωστές παραλλαγές είναι Turing complete, και ουσιαστικά απλά προσθέτουν δυνατότητες στη βασική μηχανή Turing. Άλλωστε και ένας επεξεργαστής μηχανή Turing είναι, απλά φοβερά περίεργη παραλλαγή της.
__________________
www.bedroomlan.org |
#5
|
|
||||
Διαβασα σημερα πχ οτι η SQL ειναι μια γλωσσα που δεν ειναι Turing Complete
Σε γενικες γραμμες καταννοω οτι η SQL ειναι μεν γλωσσα, αλλα δεν μπορεις να γραψεις πχ λειτουργικο συστημα με αυτη. Πώς αποδεικνύεται αυτο ομως (με τον επισημο ορισμο);
__________________
Υπάρχουν σε όλα δύο απόψεις... Αυτή που λέω εγώ, και η σωστή! |
#6
|
|
||||
Πχ αν μια γλώσσα δεν έχει δομές ελέγχου (if/goto/loops) και κάποιο τρόπο να αποθηκεύσει δεδομένα, δεν είναι turing complete. Η SQL είναι ειδική περίπτωση, όμως, γιατί ενώ από μόνη της δεν είναι καθόλου Turing complete, έχει πχ stored procedures που είναι Turing complete (σημείωση: δεν υποστηρίζουν όλοι οι SQL RDBMS stored procedures).
__________________
www.bedroomlan.org Τελευταία επεξεργασία από το χρήστη Morgul : 24-04-10 στις 01:01 |
#7
|
|
||||
Επειδή μηχανή Turing ακούμε και Turing "δεν ξέρουμε", πόσο δε και το πως αποδεικνύεται ότι είναι - δεν είναι universal , σας πειράζει να δώσω ένα βίντεο και την αντίστοιχη πηγή; http://aturingmachine.com/
|
The Following 2 Users Say Thank You to christi For This Useful Post: | ||
Archmage (16-05-10) |
#8
|
|
||||
Βέβαια, πληροφοριακά, η μηχανή Turing είναι σαν τη Γάτα του Schrödinger — είναι κάτι καθαρά θεωρητικό, και δεν σχεδιάστηκε για να υλοποιηθεί. Αν θες να δεις μια Universal Turing Machine, απλά κοίτα την κεντρική μονάδα του Η/Υ σου. Το ίδιο πράγμα είναι, απλά το τυλίγουμε με διάφορες σάλτσες για να κάνουμε κάποια πράγματα πιο γρήγορα. Πληροφοριακά, η συσκευή είναι Universal Turing Machine. Η μηχανή Turing που βλέπεις να τρέχει είναι πρόγραμμα που τρέχει μάλλον σε κάποιο απλό microcontroller. Οι περισσότεροι microcontrollers είναι RISC CPUs, και κάθε CPU είναι Universal Turing Machine. Εξ ορισμού, αυτό της επιτρέπει να εξομοιώνει άλλες μηχανές Turing, πράγμα που βλέπουμε εδώ. Από τη σκοπιά ενός θεωρητικού πληροφορικάριου (sic), αυτό είναι εξαιρετικά διασκεδαστικό, αλλά οι θεωρητικοί πληροφορικάριοι διασκεδάζουν με περίεργα πράγματα.
__________________
www.bedroomlan.org Τελευταία επεξεργασία από το χρήστη Morgul : 16-05-10 στις 12:43 |
Συνδεδεμένοι χρήστες που διαβάζουν αυτό το θέμα: 1 (0 μέλη και 1 επισκέπτες) | |
Εργαλεία Θεμάτων | |
Τρόποι εμφάνισης | |
|
|