Θεωρία υπολογισιμότητας: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας Ετικέτα: μεγάλη προσθήκη |
||
Γραμμή 101:
* Το δικτυωτό των Αναδρομικά Αριθμήσιμων Συνόλων
Όταν ο Post όρισε την έννοια ενός απλού συνόλου, ως ενός εκ νέου συνόλου με ένα άπειρο συμπλήρωμα που δεν περιέχει κανένα άπειρο σύνολο re, άρχισε τη μελέτη της δομής των αναδρομικά αριθμήσιμων συνόλων υπό ένταξη. Αυτό το πλέγμα έγινε μια καλά μελετημένη δομή. Αναδρομικά σύνολα μπορούν να οριστούν σε αυτή τη δομή από τη βασικό αποτέλεσμα ότι ένα σύνολο είναι αναδρομικό αν και μόνο αν το σύνολο και το συμπλήρωμά του είναι αναδρομικά αριθμήσιμα. Άπειρα σύνολα έχουν πάντα άπειρα αναδρομικά υποσύνολα αλλά από την άλλη πλευρά, υπάρχουν απλά σύνολα που υπάρχουν, αλλά δεν έχουν αναδρομικό υπερσύνολο. Ο Post (1944) εισήγαγε ήδη υπεραπλά και υπερυπεραπλά σύνολα. Αργότερα μέγιστα σύνολα κατασκευάστηκαν τα οποία είναι σύνολα τέτοια ώστε κάθε υπερσύνολο είναι είτε ένα πεπερασμένο παραλλαγή του συγκεκριμένου μέγιστου συνόλου ή συν-πεπερασμένο. Το αρχικό κίνητρο του Post στη μελέτη αυτού του πλέγματος ήταν να βρεθεί μια δομική αντίληψη, έτσι ώστε κάθε σύνολο που ικανοποιεί αυτή την ιδιότητα δεν είναι ούτε στο βαθμό Turing των αναδρομικών συνόλων ούτε στο βαθμό Turing του προβλήματος τερματισμού. Ο Post δεν κατάφερε να βρει τον εν λόγω κώδικα και η λύση στο πρόβλημά του εφαρμόστηκε στις μεθόδους προτεραιότητας. Ο Harrington και ο Soare (1991), βρήκαν τελικά ένα τέτοιο κώδικα.
* Προβλήματα Αυτομορφισμού
Ένα άλλο σημαντικό ζήτημα είναι η ύπαρξη αυτομορφισμών στις δομές της ανάδρομης θεωρίας . Σε μία από αυτές τις δομές, το Α είναι κάτω από Β αν και μόνο αν η διαφορά συνόλου Β - Α είναι πεπερασμένη. Τα Μέγιστα σύνολα (όπως ορίζονται στην προηγούμενη παράγραφο) έχουν την ιδιότητα ότι δεν μπορούν να είναι αυτομορφικά σε μη-μέγιστη σύνολα, δηλαδή, εάν υπάρχει ένας αυτομορφισμός των αναδρομικών αριθμητικών συνόλων σύμφωνα με τη δομή που μόλις ανεφέρθη, τότε κάθε μέγιστο σύνολο αντιστοιχίζεται σε ένα άλλο μέγιστο σύνολο. Ο Soare (1974) έδειξε ότι και το αντίστροφο ισχύει, δηλαδή, κάθε δύο μέγιστα σύνολα είναι αυτόμορφα. Έτσι, τα μέγιστα σύνολα σχηματίζουν μια τροχιά, δηλαδή, κάθε αυτομορφία διατηρεί μεγιστοποίηση και οποιαδήποτε δύο μέγιστα σύνολα μετασχηματίζονται το ένα στο άλλο από κάποια αυτομορφία. Ο Harrington έδωσε ένα ακόμη παράδειγμα μιας αυτομορφικής ιδιότητας : αυτής των δημιουργικών συνόλων, των συνόλων που έχουν πολλά-ένα ισοδύναμα με το πρόβλημα τερματισμού.
Εκτός από το πλέγμα των αναδρομικά αριθμήσιμων συνόλων, οι αυτομορφισμοί έχουν επίσης μελετηθεί για τη δομή των Turing βαθμών όλων των συνόλων, καθώς και για τη δομή των Turing βαθμών σε r.e. σύνολα. Σε αμφότερες τις περιπτώσεις, o Cooper ισχυρίζεται ότι έχει κατασκευασει μη τετριμμένους αυτομορφισμούς που χαρτογραφούν κάποιους βαθμούς σε άλλους βαθμούς. Αυτη η κατασκευή , ωστόσο, δεν έχει επαληθευτεί και ορισμένοι συνάδελφοί του πιστεύουν ότι η κατασκευή περιέχει σφάλματα και ότι το ζήτημα του κατά πόσον υπάρχει ένας τετριμμένος αυτομορφισμός των βαθμών Turing εξακολουθεί να είναι ένα από τα κύρια εκκρεμή θέματα σε αυτόν τον τομέα (Slaman και Woodin 1986, Ambos-Spies και Fejer 2006).
* Πολυπλοκότητα του Kolmogorov
Κύριο άρθρο: Kolmogorov πολυπλοκότητα
* Υπολογισμός Συχνότητας ▼
Το πεδίο της πολυπλοκότητας του Kolmogorov και της αλγοριθμικής τυχαιότητας αναπτύχθηκε κατά τη διάρκεια του 1960 και του 1970 από τους Chaitin, Kolmogorov, Levin, Martin-Löf και Σολομόνοφ (τα ονόματα δίνονται εδώ με αλφαβητική σειρά, μεγάλο μέρος της έρευνας ήταν ανεξάρτητη, και η ενότητα της έννοιας της τυχαιότητας δεν ήταν κατανοητή εκείνη τη στιγμή). Η κύρια ιδέα είναι να εξετάσει μια καθολική μηχανή Turing U και να μετρήσει την πολυπλοκότητα ενός αριθμού (ή string) x ως το μήκος της συντομότερης p εισόδου έτσι ώστε U (p) να έχει αποτέλεσμα x .Αυτή η προσέγγιση έφερε την επανάσταση στους τρόπους που καθορίζουν πότε μια άπειρη ακολουθία (ισοδύναμα, χαρακτηριστική συνάρτηση ενός υποσυνόλου των φυσικών αριθμών) είναι τυχαία ή όχι με την επίκληση της έννοια της τυχαιότητας για πεπερασμένα αντικείμενα. Η πολυπλοκότητα του Kolmogorov όχι μόνο έγινε αντικείμενο ανεξάρτητης μελέτης, αλλά εφαρμόζεται επίσης σε άλλα θέματα, όπως σε ένα εργαλείο για τη λήψη αποδείξεων. Υπάρχουν ακόμα πολλά ανοιχτά προβλήματα σε αυτόν τον τομέα. Για το λόγο αυτό, ένα πρόσφατο συνέδριο της έρευνας στον τομέα αυτό πραγματοποιήθηκε τον Ιανουάριο του 2007 και μια λίστα των ανοικτών προβλημάτων διατηρείται από τον Joseph Miller και τον Andre Nies.
Αυτός ο κλάδος της θεωρίας της αναδρομής ανέλυσε την ακόλουθη ερώτηση: Για σταθερά m και n με 0 <m <n, για την οποία λειτουργεί το Α είναι δυνατόν να υπολογιστεί και για τυχόν διαφορετικές εισόδους n x 1, x 2, ..., x n μια πλειάδα n αριθμών y 1, y 2, ..., yn έτσι ώστε τουλάχιστον το m των εξισώσεων A (x k) = y k να είναι αληθές. Τέτοια σύνολα είναι γνωστά ως (m, n) αναδρομικά σύνολα. Το πρώτο σημαντικό αποτέλεσμα σε αυτόν τον κλάδο της ανάδρομης θεωρίας είναι το αποτέλεσμα του Trakhtenbrot ότι ένα σύνολο είναι υπολογίσιμο αν είναι (m, n) ανάδρομο για κάποιο m, n με 2 m> n. Από την άλλη πλευρά, τα ημιανάδρομα σύνολα του Jockusch (τα οποία ήταν ήδη γνωστά ανεπίσημα πριν τα εισαγάγει ο Jockusch το 1968 ) αποτελούν παραδείγματα ενός συνόλου που είναι ανάδρομο κατά (m, n) αν και μόνο αν 2 m <n + 1. Υπάρχουν αναρίθμητα πολλά απο αυτά τα σύνολα και επίσης κάποια αναδρομικά αριθμητικά αλλά μη-υπολογίσιμα σύνολα του τύπου αυτού. Αργότερα, ο Degtev προέβλεψε την ιεράρχηση των αναδρομικά αριθμήσιμων συνόλων που είναι (1, n + 1), αλλά όχι (1, n). Μετά από μια μακρά φάση της έρευνας από Ρώσους επιστήμονες, το θέμα αυτό έγινε ξανά δημοφιλές στα δυτικά από την πραγματεία του Beigel για οριοθετημένα ερωτήματα, τα οποία συνδέουν τον υπολογισμό της συχνότητας με την προαναφερόμενη οριοθετημένη αναγωγή και άλλες συναφείς έννοιες. Ένα από τα σημαντικότερα αποτελέσματα ήταν Cardinality Θεωρία του Kummer η οποία αναφέρει ότι ένα σύνολο Α είναι υπολογίσιμο αν και μόνο αν υπάρχει n τέτοιο ώστε κάποιος αλγόριθμος απαριθμεί για κάθε πλειάδα των n διαφορετικούς αριθμούς μέχρι n πολλές πιθανές επιλογές αυτού του συνόλου των n αριθμών διασταυρώνεται με το Α. Αυτές οι επιλογές πρέπει να περιέχουν την πραγματική cardinality αλλά να αφήνουν έξω τουλάχιστον μια ψεύτικη.
* Επαγωγικά Συμπεράσματα
Αυτή είναι το ανάδρομο θεωρητικό παρακλάδι της θεωρίας της μάθησης. Βασίζεται στο μοντέλο της μάθησης στο όριο του Gold από το 1967 και έχει εξελιχθεί έκτοτε σε όλο και περισσότερα μοντέλα της μάθησης. Το γενικό σενάριο είναι το εξής: Λαμβάνοντας υπόψη μια κατηγορία S των υπολογίσιμων συναρτήσεων, είναι ένας μαθητής (δηλαδή, αναδρομική λειτουργία) το οποίο εξάγει για κάθε είσοδο της μορφής (f (0), f (1), ..., f (n)) μια υπόθεση. Ένας μαθητής Μ μαθαίνει μια συνάρτηση f αν και σχεδόν όλες τις υποθέσεις είναι ο ίδιος δείκτης ε της f σε σχέση με προηγούμενη συμφωνία για την αποδεκτή αρίθμηση όλων των υπολογίσιμων συναρτήσεων. Ο M μαθαίνει το S αν ο M μαθαίνει κάθε f στο S. Τα βασικά συμπεράσματα είναι ότι όλες οι αναδρομικά αριθμήμενες τάξεις των συναρτήσεων μπορούν να κατακτηθούν γνωστικά, ενώ η κατηγορία REC όλων των υπολογίσιμων συναρτήσεων δεν μπορεί να κατακτηθεί. Πολλά σχετικά μοντέλα έχουν εξεταστεί και η εκμάθηση των κατηγοριών των αναδρομικά αριθμήσιμων συνόλων από τα θετικά αποθυκευμένα στοιχεία είναι ένα θέμα που μελετήθηκε από την πρωτοποριακή εργασία του Gold απο το 1967 και μετά.
* Γενικεύσεις της υπολογισιμότητας Turing
Η ανάδρομη θεωρία περιλαμβάνει τη μελέτη των γενικευμένων εννοιών του τομέα αυτού, όπως η αριθμητική αναγωγή , η υπεραριθμιτική αναγωγή και θεωρία της α-αναδρομής , όπως περιγράφεται από τον Sacks (1990). Αυτές οι γενικευμένες έννοιες περιλαμβάνουν αναγωγές που δεν μπορούν να εκτελεστούν από μηχανές Turing, αλλά είναι παρ 'όλα αυτά φυσικά γενικεύσεις της αναγωγής του Turing . Οι μελέτες αυτές περιλαμβάνουν προσεγγίσεις για τη διερεύνηση της αναλυτικής ιεραρχίας η οποία διαφέρει από την αριθμητική ιεραρχία επιτρέποντας την ποσοτικοποίηση πάνω σε σύνολα των ακεραίων αριθμών εκτός από την ποσοτικοποίηση των ατομικών αριθμών. Οι περιοχές αυτές συνδέονται με τις θεωρίες των καλώς διεταγμένων και τις γραφικές αναπαραστάσεις. Για παράδειγμα, το σύνολο όλων των δεικτών των αναδρομικών (μη δυαδικές) αναπαραστάσεων χωρίς άπειρα κλαδιά είναι πλήρης για το επίπεδο της αναλυτικής ιεραρχίας. Τόσο η αναγωγιμότητα Turing και η υπεραριθμιτική αναγωγή είναι σημαντική στον τομέα της αποτελεσματικής περιγραφικής θεωρίας του σύνολο . Η ακόμα πιο γενική έννοια των βαθμών Κατασκευασιμότητας έχει μελετηθεί σε θεωρία συνόλων .
* Συνεχής θεωρία υπολογισιμότητας
Η Θεωρία της υπολογισιμότητας για τον ψηφιακό υπολογισμό έχει αναπτυχθεί καλά. Η Θεωρία της υπολογισιμότητας είναι λιγότερο καλά αναπτυγμένη για αναλογικό υπολογισμό που εμφανίζεται σε αναλογικούς υπολογιστές , αναλογική επεξεργασία σήματος , αναλογικά ηλεκτρονικά , νευρωνικά δίκτυα και συνεχούς χρόνου θεωρία ελέγχου διαμορφωμένη από διαφορικές εξισώσεις και συνεχή δυναμικά συστήματα (Orponen 1997, Moore 1996).
== Σχέσεις μεταξύ Προσδιορισιμότητας και Υπολογισιμότητας ==
Γραμμή 115 ⟶ 131 :
Ο κλάδος της Θεωρίας Αποδείξεων περιλαμβάνει την μελέτη της αριθμητικής δεύτερης ταξης και τα [[Αξιώματα Πεάνο]] όπως επίσης και τυπικές θεωρίες των φυσικών πιο αδύναμες από τα Αξιώματα Πεάνο.Μία μέθοδος κατηγοριοποιήσης της ισχύς αυτών των αδύναμων συστημάτων γίνεται με τον χαρακτηρισμό για ποιές υπολογίσμες συναρτήσεις το σύστημα μπορει να αποδειχθεί πλήρες(βλ. Fairtlough and Wainer (1998)).Για παράδειγμα ,στην θεμελιωδώς αναδρομική αριθμητική οποιαδήποτε συνάρτηση που ειναι πλήρης ειναι θεμελιωδώς αναδρομική ,ενώ τα Αξιώματα Πεάνο αποδεικνύουν ότι συναρτήσεις όπως η συνάρτηση του Ackermann ,οι οποίες δεν είναι θεμελιωδώς αναδρομικές ,είναι πλήρης,Επομένως δεν αποδεικνύεται για όλες τις πλήρης-υπολογίσιμες συναρτήσεις οτι ειναι πλήρης και στην Αριθμητική Πεάνο.Μάλιστα μία τέτοια συνάρτηση δίνεται απο το θεώρημα Goodstein.
Όνομα του Υποκειμένου
Το πεδίο της μαθηματικής λογικής που ασχολείται με την υπολογισιμότητα και τις γενικεύσεις της έχει χαρακτηριστεί ως «θεωρία αναδρομής» από τις πρώτες ημέρες της. Ο Robert I. Soare , ένας εξέχων ερευνητής στον τομέα, πρότεινε (Soare 1996) ότι το πεδίο θα πρέπει να ονομάζεται «θεωρία υπολογισιμότητας ". Ισχυρίζεται ότι η ορολογία του Τούρινγκ που χρησιμοποιεί τη λέξη «υπολογίσιμο» είναι πιο φυσική και πιο ευρέως κατανοητή από την ορολογία που χρησιμοποιεί τη λέξη «αναδρομική» που θεσπίστηκε από τον Kleene. Πολλοί σύγχρονοι ερευνητές έχουν αρχίσει να χρησιμοποιούν αυτή την εναλλακτική ορολογία. Αυτοί οι ερευνητές χρησιμοποιούν επίσης την ορολογία, όπως μερικά υπολογίσιμη συνάρτηση και υπολογισίμως αριθμήσιμο σύνολο αντί για μερικά αναδρομική συνάρτηση και αναδρομικά αριθμήσιμα σύνολα. Δεν έχουν όλοι οι ερευνητές αυτή την πεποίθηση, ωστόσο, όπως εξήγησε ο Fortnow και Simpson. Ορισμένοι σχολιαστές υποστηρίζουν ότι τόσο το όνομα θεωρία της αναδρομής όσο και το όνομα θεωρία της υπολογισιμότητας αποτυγχάνουν να μεταδώσουν το γεγονός ότι τα περισσότερα από τα αντικείμενα που μελετήθηκαν στη θεωρία αναδρομής δεν είναι υπολογίσιμα.
Ο Rogers (1967) πρότεινε ότι μια βασική ιδιότητα της θεωρίας αναδρομής είναι ότι τα αποτελέσματα και οι δομές της θα πρέπει να αμετάβλητες στο πλαίσιο υπολογίσιμων συναρτήσεων για τους φυσικούς αριθμούς (η πρόταση αυτή εμπνέεται από τις ιδέες του προγράμματος Erlangen στη γεωμετρία). Η ιδέα είναι ότι ένα υπολογίσιμη συνάρτηση απλώς μετονομάζει τους αριθμούς σε μια σειρά, αντί να αναγράφει κάθε δομή στο σύνολο, ακριβώς όπως και η περιστροφή του Ευκλείδειου επιπέδου δεν αλλάζει οποιαδήποτε γεωμετρική όψη των γραμμών που χαράσσονται σε αυτό. Εφόσον κάθε δύο άπειρα υπολογίσιμα σύνολα συνδέονται με υπολογίσιμη συνάρτηση, η παρούσα πρόταση προσδιορίζει όλα τα άπειρα υπολογίσιμα σύνολα (τα πεπερασμένα σύνολα υπολογίσιμα σύνολα θεωρούνται ως ασήμαντο). Σύμφωνα με τον Rogers, τα σύνολα των τόκων στη θεωρία της αναδρομής είναι τα μη-υπολογίσιμα σύνολα, χωρισμένα σε κατηγορίες ισοδυναμίας από υπολογίσιμες συναρτήσεις των ακεραίων αριθμών.
Οι Επαγγελματικές Οργανώσεις
Η κύρια επαγγελματική οργάνωση για τη θεωρία της αναδρομής είναι η Ένωση της Συμβολικής Λογικής , η οποία οργανώνει διάφορα ερευνητικά συνέδρια κάθε χρόνο. Η διεπιστημονική ερευνητική οργάνωση Υπολογισιμότητα στην Ευρώπη (CiE) διοργανώνει επίσης μια σειρά ετήσιων συνεδρίων. Το συνέδριο CiE 2012 ήταν η διάσκεψη εκατονταετίας Turing , που πραγματοποιήθηκε στο Cambridge, στο πλαίσιο του έτους Alan Turing.
== Βιβλιογραφία ==
| |||