Θεωρία υπολογισιμότητας: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 5:
Η Θεωρία της Αναδρομής συνδυάζεται με την Θεωρία των Αποδείξεων,με την Αποτελεσματική Περιγραφική Θεωρία Συνόλων, την [[Θεωρία μοντέλων|Θεωρια Μοντέλων]] και την Αφηρημένη Άλγεβρα. Μάλιστα, Θα μπορούσαμε να χαρακτηρίσουμε οτι η Θεωρία της Πολυπλοκότητας είναι γέννημα της Αναδρομικής Θεωρίας καθώς και οι δύο μοιράζονται ίδιο τεχνικό εργαλείο ,δηλαδή το Turing Machine.
Κυρίως με την Θεωρία των Αναδρομικών Συνόλων και Συναρτήσεων ο χώρος έρευνας της Θεωρίας της Αναδρομής έχει επεκταθεί σε πολλές σχετικές θεωρίες :
Η θεωρία της αναδρομής στη Μαθηματική λογική παραδοσιακά εστιαζόταν στη σχετική υπολογισιμότητα, μια γενίκευση της υπολογισιμότητας Turing,που καθορίζεται χρησιμοποιώντας μια μηχανή χρησμού Turing που παρουσιάστηκε από τον Turing(1939). Μια μηχανή χρησμού Turing, είναι μία υποθετική συσκευή, η οποία εκτός από τις παραδοσιακές ενέργειες μιας μηχανής Turing, μπορεί να κάνει ερωτήσεις για ένα συγκεκριμένο σύνολο ακέραιων αριθμών.Η μηχανή oracle μπορεί να κάνει ερωτήσεις της μορφής <<Είναι το n στο σύνολο oracle;>> Κάθε ερώτηση θα απαντάται άμεσα σωστά ακόμη και αν το σύνολο δεν είναι υπολογίσιμο.
Ανεπίσημα, ένα σύνολο ακεραίων αριθμών Α είναι αναγώγιμο σε ένα σύνολο Β αν υπάρχει μια μηχανή oracle που σωστά εάν οι αριθμοί είναι στο Α όταν εκτελούνται με το Β, όπως στο σύνολο oracle (σε αυτη την περίπτωση, το σύνολο Α επίσης λέγεται ότι είναι (σχετικά) υπολογίσιμο από το Β και το Β μπορεί να αναχθεί στο Α τότε το σύνολο λέγεται ότι έχουν τον ίδιο βαθμό Turing (ονομάζεται επίσης βαθμός unsolvability). Ο βαθμός Turing ενός συνόλου δίνει ένα ακριβές μέτρο του πόσο μη-υπολογίσιμο είναι το σύνολο.
Τα φυσικά παραδείγματα των συνόλων που δεν είναι υπολογίσιμα, συμπεριλαμβανομένων πολλών διαφορετικών συνόλων που κωδικοποιούν παραλλαγές του προβλήματος τερματισμού, έχουν δύο κοινές ιδιότητες:
1.Είναι αναδρομικά αριθμήσιμα, και
2.Κάθε ένα μπορεί να μεταφραστεί σε οποιοδήποτε άλλο μέσω πολλών-μίας μείωσης.Δηλαδή, δεδομένων τέτοιων συνόλων Α και Β, υπάρχει μία συνολική λειτουργία τέτοια ώστε Α={x:f(x)∈B} Αυτά τα σύνολα λέγεται ότι είναι πολλές-ένα ισοδύναμο (ή m-ισοδύναμο).
Οι πολλές-μια μειώσεις είναι «ισχυρότερες» από τις μειώσεις Turing: εάν ένα σύνολο Α είναι αναγώγιμο σε ένα σύνολο Β, τότε το Α μπορεί να αναχθεί σε B, αλλά το αντίστροφο δεν είναι πάντα εφικτό. Παρά το γεγονός ότι τα φυσικά παραδείγματα μη-υπολογίσιμων συνόλων είναι όλα πολλά-ένα ισοδύναμα, είναι δυνατόν να κατασκευαστούν αναδρομικά αριθμήσιμα σύνολα Α και Β, έτσι ώστε το Α να ανάγεται στο Β, αλλά όχι πολλά-ένα αναγώγιμο στο Β. Μπορεί να δειχθεί ότι κάθε αναδρομικά αριθμήσιμα σύνολο είναι πολλά-ένα αναγώγιμο στο πρόβλημα τερματισμού, και έτσι το πρόβλημα τερματισμού είναι το πιο περίπλοκο αναδρομικά αριθμήσιμα σύνολο σε σχέση με πολλές-ένα αναγωγές και με αναφορά προς την αναγωγή Turing. Ο Post (1944) ρώτησε αν κάθε αναδρομικά αριθμήσιμα σύνολο είναι είτε υπολογίσιμο ή Turing ισοδύναμο με το πρόβλημα τερματισμού, δηλαδή, αν δεν υπάρχει αναδρομικά αριθμήσιμα σύνολο με ένα βαθμό Turing ενδιάμεσο μεταξύ των δύο.
Ως ενδιάμεσα αποτελέσματα, ο Post όρισε ακέραιους τύπους αναδρομικά αριθμήσιμων συνόλων όπως τα απλά,υπεραπλά και υπέρ-υπεραπλά σύνολα. Ο Post έδειξε ότι αυτά τα σύνολα είναι αυστηρά μεταξύ των υπολογίσιμων συνόλων και του προβλήματος τερματισμού σε σχέση με την πολλές-μια αναγωγιμότητα. Ο Post έδειξε επίσης ότι ορισμένοι από αυτούς είναι απολύτως ενδιάμεσο προϊόν υπό άλλες έννοιες αναγωγιμότητας ισχυρότερες από ότι η αναγωγιμότητα του Turing . Αλλά ο Post άφησε ανοιχτό το κύριο πρόβλημα της ύπαρξης των αναδρομικά αριθμήσιμων συνόλων με ενδιάμεσο βαθμό Turing,το πρόβλημα αυτό έγινε γνωστό ως το πρόβλημα του Post. Μετά από δέκα χρόνια, ο Kleene και ο Post το 1954 έδειξαν ότι υπάρχουν ενδιάμεσοι βαθμοί Turing μεταξύ αυτών τα υπολογίσιμα σύνολα και το πρόβλημα τερματισμού, αλλά απέτυχαν να δείξουν ότι κάποια από αυτές τις μοίρες περιλαμβάνει κάποιο αναδρομικά αριθμήσιμα σύνολο. Πολύ σύντομα μετά από αυτό, ο Friedberg και ο Muchnik ανεξάρτητα έλυσαν το πρόβλημα του Post κατά τη διαπίστωση της ύπαρξης αναδρομικά αριθμήσιμων συνόλων με ενδιάμεσο βαθμό. Αυτή το πρωτοποριακό αποτέλεσμα άνοιξε μια ευρεία μελέτη των βαθμών Turing των αναδρομικά αριθμήσιμων συνόλων που αποδείχθηκε ότι έχουν μια πολύ περίπλοκη και μη τετριμμένη δομή.
Υπάρχουν αμέτρητα πολλά σύνολα που δεν είναι αναδρομικά αριθμήσιμα, καθώς και η διερεύνηση των Turing βαθμών όλων των συνόλων είναι τόσο κεντρική στη θεωρία αναδρομής και τη διερεύνηση των αναδρομικά αριθμήσιμων βαθμών Turing. Πολλοί βαθμοί με ειδικές ιδιότητες κατασκευάστηκαν ως υπεράνοσοι χωρίς βαθμούς όπου κάθε λειτουργία υπολογίσιμη σε σχέση με αυτό το βαθμό είναι μεγενθυμένη από μια υπολογίσιμη συνάρτηση. Υψηλούς βαθμούς σε σχέση με τους οποίους μπορεί κανείς να υπολογίσει μια συνάρτηση f η οποία κυριαρχεί σε κάθε υπολογίσιμη συνάρτηση g,με την έννοια ότι υπάρχει μια σταθερά c, ανάλογη με τη g τέτοια ώστε g(x)<f(x) για κάθε x>c , τυχαίοι βαθμοί που περιέχουν αλγοριθμικά τυχαία σύνολα. 1-γενικοί βαθμοί ενός 1-γενικού συνόλου.
Η μελέτη των αυθαίρετων (όχι κατ 'ανάγκη αναδρομικά αριθμήσιμων) βαθμών Turing περιλαμβάνει τη μελέτη του άλματος Turing. Λαμβάνοντας υπόψη ένα σύνολο A, το Turing άλμα του Α είναι ένα σύνολο των φυσικών αριθμών που κωδικοποιεί μια λύση για το πρόβλημα τερματισμού για τις μηχανές Turing που τρέχουν με χρησμό Α. Το Turing άλμα του κάθε σετ είναι πάντα με υψηλότερο βαθμό Turing από το αρχικό σύνολο, και ένα θεώρημα του Friedburg δείχνει ότι κάθε σύνολο που υπολογίζει το πρόβλημα τερματισμού μπορεί να ληφθεί ως Turing άλμα του ενός άλλου συνόλου. Το θεώρημα του Post, καθιερώνει μια στενή σχέση μεταξύ της λειτουργίας του άλματος Turing και της αριθμητικής ιεραρχίας , η οποία είναι μια κατάταξη ορισμένων υποσυνόλων των φυσικών αριθμών με βάση το πόσο μπορούν να οριστικοποιηθούν στην αριθμητική.
Μεγάλο μέρος της πρόσφατης έρευνας για τους βαθμούς Turing έχει επικεντρωθεί στη συνολική δομή του συνόλου των βαθμών Turing και το σύνολο των βαθμών που περιέχουν αναδρομικά αριθμήσιμα σύνολα.Ένα βαθύ θεώρημα του Shore και Slaman (1999) αναφέρει ότι η χαρτογράφηση της συνάρτησης βαθμού x με το βαθμό του άλματος Turing της,είναι προσδιορίσιμο με τη μερική σειρά των βαθμών Turing. Μια πρόσφατη έρευνα από τους Ambos-Spies και Fejer (2006) παρέχει μια επισκόπηση της έρευνας και της ιστορικής εξέλιξης της.
Η εν εξελίξει τομέα της έρευνας στη θεωρία αναδρομής μελετά τις σχέσεις αναγωγισιμότητας πλην της αναγωγισιμότητας του Turing . Ο Post (1944) εισήγαγε αρκετές ισχυρές αναγωγισιμότητες, που ονομάστηκαν έτσι επειδή υπαινίσσονται τραπέζι αληθινής αναγωγισιμότητας. Μια μηχανή Turing για την εφαρμογή μιας ισχυρής αναγωγισιμότητας θα υπολογίσει μια συνολική συνάρτηση ανεξάρτητα από το με ποιό oracle παρουσιάζεται. Ασθενείς αναγωγές είναι εκείνες όπου η διαδικασία μείωσης δεν μπορεί να τερματιστεί για όλα τα σύνολα αριθμών. Η αναγωγή του Turing είναι ένα παράδειγμα.
Όπως τις:
Το Α είναι το ένα προς ένα αναγώγιμο (ή 1-αναγώγιμο) στο Β αν υπάρχει μια συνολική υπολογίσιμη αμφιμονοσήμαντη συνάρτηση τέτοια ώστε κάθε n είναι στην Α αν και μόνο αν το f(n) είναι στο Β.
Αυτό είναι ουσιαστικά η αναγωγή ένα προς ένα χωρίς τον περιορισμό ότι το f είναι αμφιμονοσήμαντο. Το Α είναι πολλοί προς ένα αναγώγιμο (ή m-αναγώγιμη) στο Β, αν υπάρχει μια συνολικά υπολογίσιμη συνάρτηση, έτσι ώστε κάθε n ανήκει στο A αν και μόνο αν το f(n) είναι στο Β.
Το Α είναι αληθινά αναγώγιμο σε πίνακα Β,αν το Α είναι αναγώγιμο κατά Turing στο Β μέσω της μηχανής Turing που υπολογίζει μια συνολική συνάρτηση. Λόγω του συμπαγούς του Cantor χώρου , αυτό είναι ισοδύναμο με το να πούμε ότι η μείωση παρουσιάζει έναν ενιαίο κατάλογο ερωτήσεων (εξαρτώμενο μόνο από την είσοδο) στο oracle ταυτόχρονα,και στη συνέχεια, έχοντας δει τις απαντήσεις τους είναι σε θέση να παράγει ένα αποτέλεσμα χωρίς να ζητήσει πρόσθετες ερωτήσεις,ανεξάρτητα με την απάντησης του oracle των αρχικών ερωτημάτων. Πολλές παραλλαγές του πίνακα αληθινής αναγωγής έχουν επίσης μελετηθεί.
Περαιτέρω αναγωγές(θετική,διαζευκτική,συνδετική,γραμμική και οι αδύναμες και δυνατές μορφές τους) συζητούνται στο άρθρο Μείωση (θεωρία αναδρομής) .
Η μεγάλη έρευνα για ισχυρές αναγωγές έγινε για να συγκρίνουν τις θεωρίες τους, τόσο για την κλάση όλων των αναδρομικά αριθμήσιμων συνόλων, καθώς και για την τάξη όλων των υποσυνόλων των φυσικών αριθμών. Επιπλέον, οι σχέσεις μεταξύ των αναγωγών έχει μελετηθεί. Για παράδειγμα, είναι γνωστό ότι κάθε βαθμός Turing είναι είτε ένας βαθμός από αληθινό πίνακα ή είναι η ένωση των απείρων πολλών βαθμών από αληθινούς πίνακες.
Οι αναγωγές που είναι ασθενέστερες από ότι η αναγωγή του Turing (δηλαδή, αναγωγές που υπονοούνται από την αναγωγή του Turing) έχουν επίσης μελετηθεί.Οι πιο γνωστές είναι αριθμητικές αναγωγές και υπεραριθμητική αναγωγή.Αυτές οι αναγωγές συνδέονται στενά με την οριστικοποίηση πάνω από το καθιερωμένο μοντέλο της αριθμητικής.
Ο Ράις έδειξε ότι για κάθε μη τετριμμένη κατηγορία C (η οποία περιέχει ορισμένα αλλά όχι όλα τα σύνολα) στο ενδεικτικό σύνολο E = {e: το e στο We είναι στο C} έχει την ιδιότητα ότι είτε το πρόβλημα τερματισμού ή το συμπλήρωμά της είναι πολλές -ένα αναγώγιμο στο E, δηλαδή, μπορεί να χαρτογραφηθούν με τη χρήση πολλών-μίας αναγωγής έως Ε (βλ. θεώρημα της Ράις για περισσότερες λεπτομέρειες). Όμως,πολλά από αυτά τα ενδεικτικά σύνολα είναι ακόμη πιο περίπλοκα από ότι το πρόβλημα τερματισμού.Τα εν λόγω είδη συνόλων μπορούν να ταξινομηθούν χρησιμοποιώντας την αριθμητική ιεραρχία.Για παράδειγμα,το ενδεικτικό σύνολο FIN της τάξης όλων των πεπερασμένων συνόλων είναι στο επίπεδο Σ2 , το ενδεικτικό σύνολο REC της τάξης όλων των αναδρομικών συνόλων είναι στο επίπεδο Σ3,το ενδεικτικό σύνολο COFIN όλων των ομοτελικών συνόλων είναι επίσης στο επιπέδου Σ3 και το ενδεικτικό σύνολο COMP της κατηγορίας όλων των ολοκληρωμένων συνόλων Turing στο Σ4.Αυτά τα επίπεδα ιεραρχίας ορίζονται επαγωγικά, Σn+1 και περιέχονται ακριβώς όλα τα σύνολα που είναι αναδρομικά αριθμήσιμα σε σχέση με το Σn.Το Σ1 περιέχει τα αναδρομικά αριθμήσιμα σύνολα.Τα ενδεικτικά σύνολα που δίνονται εδώ είναι πλήρεις ακόμη και για τα επίπεδά τους,δηλαδή όλα τα σύνολα σε αυτά τα επίπεδα μπορεί να είναι πολλά προς ένα αναγώγιμα στα ενδεικτικά δοσμένα σύνολα.
'''Αντίστροφα μαθηματικά'''
Κύριο άρθρο: Αντίστροφα μαθηματικά
Το πρόγραμμα των αντιστρόφων Μαθηματικών ρωτά ποια αξιώματα υπαρκτά από τα σύνολα είναι αναγκαία για να αποδειχθεί συγκεκριμένα θεωρήματα των μαθηματικών σε υποσυστήματα της αριθμητικής της δεύτερης τάξης.Η μελέτη αυτή ξεκίνησε από τον Harvey Friedman και μελετήθηκε λεπτομερώς από τον Stephen Simpson και άλλους.Ο Simpson (1999) δίνει μια λεπτομερή συζήτηση για το πρόγραμμα.Τα αξιώματα της ύπαρξης των συνόλων υπό ερώτηση αντιστοιχούν ανεπίσημα σε αξιώματα που λένε ότι το δυναμοσύνολο των ακέραιων αριθμών είναι κλειστό υπό διάφορες έννοιες αναγωγής.Το πιο αδύναμο τέτοιο αξίωμα που έχει μελετηθεί σε αντίστροφα μαθηματικά είναι η αναδρομική κατανόηση,η οποία αναφέρει ότι το δυναμοσύνολο των ακεραίων είναι κλειστό υπό την αναγωγή Turing.
'''Αρίθμηση'''
Η αρίθμηση είναι μια απαρίθμηση των συναρτήσεων.Έχει δύο παραμέτρους,e και χ και εξάγει την τιμή της συνάρτησης e στην αρίθμηση για την είσοδο x. Οι αριθμήσεις μπορεί να είναι μερικά-αναγώγιμες αν και ορισμένα από τα μέλη τους είναι συνολικά αναγώγιμα, δηλαδή, υπολογίσιμες συναρτήσεις.Παραδεκτές αριθμήσεις είναι εκείνες στις οποίες όλες οι άλλες μπορούν να μεταφραστούν.Μια αρίθμηση Friedberg (που ονομάζεται από αυτόν που την ανακάλυψε)είναι η ένα προς ένα αρίθμηση όλων των επιμέρους-αναδρομικών συναρτήσεων,είναι κατ 'ανάγκην μια μη παραδεκτή αρίθμηση.Μεταγενέστερη έρευνα ασχολήθηκε επίσης με αριθμήσεις από άλλες κατηγορίες όπως τις τάξεις των αναδρομικά αριθμήσιμων συνόλων. Ο Goncharov ανακάλυψε για παράδειγμα μια κατηγορία αναδρομικά αριθμήσιμων συνόλων για τα οποία οι αριθμήσεις εμπίπτουν σε δύο κατηγορίες ακριβώς σε σχέση με τους αναδρομικούς ισομορφισμούς.
Για περαιτέρω επεξήγηση, βλ. την ενότητα πρόβλημα δημοσίευση και τη μέθοδο προτεραιότητας στο άρθρο βαθμός Turing.
Το πρόβλημα του Post λύθηκε με μια μέθοδο που ονομάζεται η μέθοδος κατά προτεραιότητας,μια απόδειξη χρήση αυτής της μεθόδου ονομάζεται επιχείρημα προτεραιότητας.Αυτή η μέθοδος χρησιμοποιείται κυρίως για την κατασκευή αναδρομικά αριθμήσιμων συνόλων με συγκεκριμένες ιδιότητες.Για να χρησιμοποιηθεί αυτή η μέθοδος,οι επιθυμητές ιδιότητες του συνόλου που πρόκειται να κατασκευαστεί χωρίστηκαν σε έναν άπειρο κατάλογο των στόχων,που είναι γνωστός ως απαιτήσεις, έτσι ώστε ικανοποιώντας όλες τις απαιτήσεις θα κάνει το κατσκευασμένο σύνολο να έχει τις επιθυμητές ιδιότητες.Κάθε απαίτηση έχει εκχωρηθεί σε ένα φυσικό αριθμό που αντιπροσωπεύει την προτεραιότητα της απαίτησης, έτσι το 0 αποδίδεται στην πιο σημαντική προτεραιότητα,το 1 στη δεύτερη πιο σημαντική,και ούτω καθεξής.Το σύνολο στη συνέχεια κατασκευάζεται σε στάδια, σε κάθε στάδιο προσπαθεί να ικανοποιήσει μία ή περισσότερες από τις απαιτήσεις, είτε με την προσθήκη αριθμών στο σύνολο ή με την απαγόρευση των αριθμών από το σύνολο, έτσι ώστε το τελικό σύνολο να ικανοποιεί την απαίτηση.Μπορεί να συμβεί να ικανοποιείται μία απαίτηση και αυτό να προκαλεί τη μη ικανοποίηση μιας άλλης,η σειρά προτεραιότητας χρησιμοποιείται για να αποφασιστεί τι πρέπει να γίνει σε μια τέτοια περίπτωση.
Τα επιχειρήματα Προτεραιότητας έχουν χρησιμοποιηθεί για να λύσουν πολλά προβλήματα στη θεωρία αναδρομής, και έχουν ταξινομηθεί σε μια ιεραρχία με βάση την πολυπλοκότητά τους (Soare 1987).Επειδή τα περίπλοκα επιχειρήματα προτεραιότητας μπορεί να είναι τεχνικά και δύσκολα να ακολουθηθούν, παραδοσιακά θεωρείται σκόπιμο να αποδειχτούν τα αποτελέσματα χωρίς επιχειρήματα προτεραιότητας, ή να διαπιστώσουμε αν τα αποτελέσματα που αποδείχθηκαν με επιχειρήματα προτεραιότητας μπορούν επίσης να αποδειχθούν χωρίς αυτά.Για παράδειγμα, ο Kummer δημοσίευσε ένα έγγραφο σε μια απόδειξη για την ύπαρξη της αρίθμηση του Friedberg χωρίς τη χρήση της μεθόδου προτεραιότητας.
▲* Άλλες Αναγωγισιμότητες .Όπως τις:
▲# Μία προς μία αναγωγισιμότητα
▲# Πολλές προς μία αναγωγισιμότητα
▲# Αναγωγισιμότητα του Πίνακα Αληθείας
▲* Το Θεώρημα του Rice και η Αριθμητική Ιεραρχία
▲* Η μέθοδος της Προτεραιότητας
* Το δικτυωτό των Αναδρομικά Αριθμήσιμων Συνόλων
* Προβλήματα Αυτομορφισμού
| |||