Θεωρία υπολογισιμότητας: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 49:
Η θεωρία της αναδρομής στη Μαθηματική λογική παραδοσιακά εστιαζόταν στη σχετική υπολογισιμότητα, μια γενίκευση της υπολογισιμότητας Turing,που καθορίζεται χρησιμοποιώντας μια μηχανή χρησμού Turing που παρουσιάστηκε από τον Turing(1939). Μια μηχανή χρησμού Turing, είναι μία υποθετική συσκευή, η οποία εκτός από τις παραδοσιακές ενέργειες μιας μηχανής Turing, μπορεί να κάνει ερωτήσεις για ένα συγκεκριμένο σύνολο ακέραιων αριθμών.Η μηχανή oracle μπορεί να κάνει ερωτήσεις της μορφής <<Είναι το n στο σύνολο oracle;>> Κάθε ερώτηση θα απαντάται άμεσα σωστά ακόμη και αν το σύνολο δεν είναι υπολογίσιμο.
Ανεπίσημα, ένα σύνολο ακεραίων αριθμών Α είναι αναγώγιμο σε ένα σύνολο Β αν υπάρχει μια μηχανή oracle που σωστά εάν οι αριθμοί είναι στο Α όταν εκτελούνται με το Β, όπως στο σύνολο oracle (σε αυτη την περίπτωση, το σύνολο Α επίσης λέγεται ότι είναι (σχετικά) υπολογίσιμο από το Β και το Β μπορεί να αναχθεί στο Α τότε το σύνολο λέγεται ότι έχουν τον ίδιο [[βαθμός Turing|βαθμό Turing]] (ονομάζεται επίσης βαθμός unsolvability). Ο βαθμός Turing ενός συνόλου δίνει ένα ακριβές μέτρο του πόσο μη-υπολογίσιμο είναι το σύνολο.
Τα φυσικά παραδείγματα των συνόλων που δεν είναι υπολογίσιμα, συμπεριλαμβανομένων πολλών διαφορετικών συνόλων που κωδικοποιούν παραλλαγές του προβλήματος τερματισμού, έχουν δύο κοινές ιδιότητες:
1.Είναι
2.Κάθε ένα μπορεί να μεταφραστεί σε οποιοδήποτε άλλο μέσω πολλών-μίας μείωσης.Δηλαδή, δεδομένων τέτοιων συνόλων Α και Β, υπάρχει μία συνολική λειτουργία τέτοια ώστε Α={x:f(x)∈B} Αυτά τα σύνολα λέγεται ότι είναι πολλές-ένα ισοδύναμο (ή m-ισοδύναμο).
| |||