Διαφορά μεταξύ των αναθεωρήσεων του «Θεωρία υπολογισιμότητας»

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

επεξεργασίες