Acrobase  

Καλώς ήρθατε στην AcroBase.
Δείτε εδώ τα πιο πρόσφατα μηνύματα από όλες τις περιοχές συζητήσεων, καθώς και όλες τις υπηρεσίες της AcroBase.
H εγγραφή σας είναι γρήγορη και εύκολη.

Επιστροφή   Acrobase > Υπολογιστές και Τεχνολογία > Τεχνολογικές ειδήσεις
Ομάδες (Groups) Τοίχος Άρθρα acrobase.org Ημερολόγιο Φωτογραφίες Στατιστικά

Notices

Δεν έχετε δημιουργήσει όνομα χρήστη στην Acrobase.
Μπορείτε να το δημιουργήσετε εδώ

Απάντηση στο θέμα
 
Εργαλεία Θεμάτων Τρόποι εμφάνισης
  #1  
Παλιά 08-12-09, 21:59
Το avatar του χρήστη Gildor
Gildor Ο χρήστης Gildor δεν είναι συνδεδεμένος
High Elf
 

Τελευταία φορά Online: 08-05-17 14:17
Φύλο: Δεν έχω αποφασίσει ακόμα
Η διαθεσή μου τώρα:
μηχανη τουρινγκ

Πως αποδεικνυεται οτι μια μηχανη Τουρινγκ ειναι Universal?

Διαβαζα ολο το βραδυ χτες, δεν εβγαλα νοημα
__________________
Υπάρχουν σε όλα δύο απόψεις...
Αυτή που λέω εγώ, και η σωστή!
Απάντηση με παράθεση
  #2  
Παλιά 10-12-09, 17:44
Το avatar του χρήστη Morgul
Morgul Ο χρήστης Morgul δεν είναι συνδεδεμένος
Άσωτος διαχειριστής
 

Τελευταία φορά Online: 26-03-22 21:02
Φύλο: Δεν έχω αποφασίσει ακόμα
Universal Turing Machine είναι μια μηχανή Turing ικανή να εκτελέσει οποιαδήποτε άλλη μηχανή Turing με κατάλληλη υλοποίηση.

Προφανώς λόγω της χρήστης του «οποιαδήποτε», η απόδειξή σου πρέπει να είναι απαγωγή εις άτοπο της θέσης ότι υπάρχει μηχανή Turing που η υποτιθέμενα Universal μηχανή σου δε μπορεί να εκτελέσει. Αυτό κάνει πολλές τέτοιες αποδείξεις εξαιρετικά δύσκολες (αν όχι αδύνατες).

Ομολογουμένως δε θυμάμαι τώρα πώς κάναμε τις αποδείξεις για περιπτώσεις UTM, αλλά οι περισσότερες αποδείξεις με μηχανές Turing βγαίνουν απαγωγικά: παίρνεις τη μηχανή Turing σου και αποδεικνύεις ότι με κατάλληλα τεχνάσματα, η μηχανή αυτή είναι ισοδύναμη σε δυνατότητες με μια συμβατική μηχανή Turing. Αυτό το δείχνεις κατασκευάζοντας μια μηχανή Turing που εμπεριέχει τις δυνατότητες της άλλης μηχανής.

Σε μπέρδεψα περισσότερο τώρα, έτσι;
__________________
www.bedroomlan.org
Απάντηση με παράθεση
  #3  
Παλιά 10-12-09, 21:29
Το avatar του χρήστη Gildor
Gildor Ο χρήστης Gildor δεν είναι συνδεδεμένος
High Elf
 

Τελευταία φορά Online: 08-05-17 14:17
Φύλο: Δεν έχω αποφασίσει ακόμα
Η διαθεσή μου τώρα:
τι εννοεις "οποιαδηποτε αλλη μηχανη"; Οταν λεμε "μηχανη Τουρινγκ" ενα πραγμα δεν εννοουμε;

(αυτη με την απειρη λωριδα)
__________________
Υπάρχουν σε όλα δύο απόψεις...
Αυτή που λέω εγώ, και η σωστή!
Απάντηση με παράθεση
  #4  
Παλιά 10-12-09, 23:37
Το avatar του χρήστη Morgul
Morgul Ο χρήστης Morgul δεν είναι συνδεδεμένος
Άσωτος διαχειριστής
 

Τελευταία φορά Online: 26-03-22 21:02
Φύλο: Δεν έχω αποφασίσει ακόμα
Αρχική Δημοσίευση από Gildor Εμφάνιση μηνυμάτων
τι εννοεις "οποιαδηποτε αλλη μηχανη"; Οταν λεμε "μηχανη Τουρινγκ" ενα πραγμα δεν εννοουμε;

(αυτη με την απειρη λωριδα)
Υπάρχουν πολλές παραλλαγές. Πολλαπλές ταινίες, ταινίες πολλαπλών διαστάσεων, μηχανές που μπορούν να αφήνουν την κεφαλή στάσιμη (δ=0, όχι μόνο δ=-1 ή δ=+1), πολλαπλές κεφαλές ανά ταινία, κλπ κλπ κλπ.

Όλες οι γνωστές παραλλαγές είναι Turing complete, και ουσιαστικά απλά προσθέτουν δυνατότητες στη βασική μηχανή Turing. Άλλωστε και ένας επεξεργαστής μηχανή Turing είναι, απλά φοβερά περίεργη παραλλαγή της.
__________________
www.bedroomlan.org
Απάντηση με παράθεση
  #5  
Παλιά 24-04-10, 00:50
Το avatar του χρήστη Gildor
Gildor Ο χρήστης Gildor δεν είναι συνδεδεμένος
High Elf
 

Τελευταία φορά Online: 08-05-17 14:17
Φύλο: Δεν έχω αποφασίσει ακόμα
Η διαθεσή μου τώρα:
Διαβασα σημερα πχ οτι η SQL ειναι μια γλωσσα που δεν ειναι Turing Complete

Σε γενικες γραμμες καταννοω οτι η SQL ειναι μεν γλωσσα, αλλα δεν μπορεις να γραψεις πχ λειτουργικο συστημα με αυτη. Πώς αποδεικνύεται αυτο ομως (με τον επισημο ορισμο);
__________________
Υπάρχουν σε όλα δύο απόψεις...
Αυτή που λέω εγώ, και η σωστή!
Απάντηση με παράθεση
  #6  
Παλιά 24-04-10, 00:58
Το avatar του χρήστη Morgul
Morgul Ο χρήστης Morgul δεν είναι συνδεδεμένος
Άσωτος διαχειριστής
 

Τελευταία φορά Online: 26-03-22 21:02
Φύλο: Δεν έχω αποφασίσει ακόμα
Αρχική Δημοσίευση από Gildor Εμφάνιση μηνυμάτων
Διαβασα σημερα πχ οτι η SQL ειναι μια γλωσσα που δεν ειναι Turing Complete

Σε γενικες γραμμες καταννοω οτι η SQL ειναι μεν γλωσσα, αλλα δεν μπορεις να γραψεις πχ λειτουργικο συστημα με αυτη. Πώς αποδεικνύεται αυτο ομως (με τον επισημο ορισμο);
Σε πολύ γενικούς όρους (κι επειδή τώρα είναι αργά και δεν έχω κοιμηθεί και είμαι καμμένος) για να είναι μια γλώσσα Turing complete πρέπει να περιγράφει μηχανές Turing, και όλες οι μηχανές Turing πρέπει να μπορούν να περιγραφούν στη γλώσσα (διπλή συνεπαγωγή).

Πχ αν μια γλώσσα δεν έχει δομές ελέγχου (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  
Παλιά 15-05-10, 23:13
Το avatar του χρήστη christi
christi Ο χρήστης christi δεν είναι συνδεδεμένος
Οργανωτής Club
 

Τελευταία φορά Online: 12-12-17 20:48
Φύλο: Γυναίκα
Επειδή μηχανή Turing ακούμε και Turing "δεν ξέρουμε", πόσο δε και το πως αποδεικνύεται ότι είναι - δεν είναι universal , σας πειράζει να δώσω ένα βίντεο και την αντίστοιχη πηγή; http://aturingmachine.com/

__________________
.
Safeline / Saferinternet
γραμμή βοήθειας 210 600 7686
Απάντηση με παράθεση
The Following 2 Users Say Thank You to christi For This Useful Post:
Archmage (16-05-10)
  #8  
Παλιά 16-05-10, 12:37
Το avatar του χρήστη Morgul
Morgul Ο χρήστης Morgul δεν είναι συνδεδεμένος
Άσωτος διαχειριστής
 

Τελευταία φορά Online: 26-03-22 21:02
Φύλο: Δεν έχω αποφασίσει ακόμα
Αρχική Δημοσίευση από christi Εμφάνιση μηνυμάτων
Επειδή μηχανή Turing ακούμε και Turing "δεν ξέρουμε", πόσο δε και το πως αποδεικνύεται ότι είναι - δεν είναι universal , σας πειράζει να δώσω ένα βίντεο και την αντίστοιχη πηγή;
Εξαιρετική η δουλειά του κατασκευαστή!!! Πολύ διασκεδαστικό το ότι γράφει τα σύμβολα στην ταινία σε μορφή αναγνώσιμη από άνθρωπο.

Βέβαια, πληροφοριακά, η μηχανή 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 επισκέπτες)
 
Εργαλεία Θεμάτων
Τρόποι εμφάνισης

Δικαιώματα - Επιλογές
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is σε λειτουργία
Τα Smilies είναι σε λειτουργία
Ο κώδικας [IMG] είναι σε λειτουργία
Ο κώδικας HTML είναι σε λειτουργία

Που θέλετε να σας πάμε;


Όλες οι ώρες είναι GMT +3. Η ώρα τώρα είναι 14:18.



Forum engine powered by : vBulletin Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.