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

καμία σύνοψη επεξεργασίας
Η '''Θεωρία της Υπολογισιμότητας''' ή '''Θεωρία της Αναδρομής''', είναι ένας κλάδος της [[μαθηματική λογική|μαθηματικής λογικής]], της [[πληροφορική]]<nowiki/>ς και της [[Θεωρία υπολογισμού|θεωρίας υπολογισμού]] που προήλθε από την έρευνα των υπολογίσιμων συναρτήσεων και του βαθμού Turing(=βαθμος μη επιλυσιμότητας) στα μέσα της δεκαετίας του 1930.
 
Τα βασικά ερωτήματα που απευθύνονται από την Θεωρία Αναδρομής είναι "Τι σημαίνει για μια συνάρτηση, ορισμένη στους [[φυσικός αριθμός|φυσικούς αριθμού]]<nowiki/>ς,ότι είναι υπολογίσιμη;" και "Πώς μπορούν μη-υπολογίσιμες συναρτήσεις να κατηγοριοποιηθούν ιεραρχικά ανάλογα με το βαθμό μη-υπολογισιμότητας τους;". Η απάντηση σε αυτές τις ερωτήσεις οδήγησε σε μία πλούσια θεωρία η οποία ακόμη απασχολεί τους επιστήμονες.Το πεδίο των ερευνών αυτών έχει διευρυνθεί από τότε και πλέον περιέχει την έρευνα της γενικευμένης υπολογισιμότητας και προσδιορισιμότητας. Αξιοσημείωτη είναι η εφεύρεση του κεντρικού συνδυαστικού αντικειμένου της Αναδρομικής Θεωρίας,δηλαδή το Universal Turing Machine,το οποίο προηγείται και προκαθορίζει την εφεύρεση των σύγχρονων υπολογιστών. Ιστορικά ,η έρευνα των αλγοριθμικά undecidable συνόλων και συναρτήσεων προέκυψε από διάφορα μαθηματικά προβλήματα που κατέληγαν undecidable. Υπάρχουν πολλές εφαρμογές αυτής της θεωρίας σε άλλους κλάδους των μαθηματικών που δεν επικεντρώνονται απαραίτητα στην undecidability.Στις πρώτες εφαρμογές της περιλαμβάνονταν Higman's embedding theorem ,το οποίο συνδέει την Αναδρομική Θεωρία με την Θεωρία των Ομάδων που ήταν αποτέλεσνμααποτέλεσμα των Michael O. Rabin και Anatoly Maltsev στην αλγοριθμική παρουσίαση της άλγεβρας αλλά και την αρνητική λύση του Hilbert's Tenth Problem. Οι πιο νέες εφαρμογές περιλαμβάνουν την αλγοριθμική τυχαιότητα που αποτελεί έρευνα του Theodore Allen Slaman ,ο οποίος εφάρμοσε αναδρομικές-θεωρητικές μεθόδους για να επιλύσει προβλήματα [[Αλγεβρική γεωμετρία|Αλγεβρικής Γεωμετρίας]] και η νεότερη του δουλειά εστιάζεται στους κανονικούς αριθμούς για να λύσει προβλήματα της Αναλυτικής Θεωρίας Αριθμών.
 
Η Θεωρία της Αναδρομής συνδυάζεται με την Θεωρία των Αποδείξεων,με την Αποτελεσματική Περιγραφική Θεωρία Συνόλων, την [[Θεωρία μοντέλων|Θεωρια Μοντέλων]] και την Αφηρημένη Άλγεβρα. Μάλιστα, Θα μπορούσαμε να χαρακτηρίσουμε ότι η Θεωρία της Πολυπλοκότητας είναι γέννημα της Αναδρομικής Θεωρίας καθώς και οι δύο μοιράζονται ίδιο τεχνικό εργαλείο ,δηλαδή τη μηχανή Turing.
 
Η Θεωρία της Αναδρομής συνδυάζεται με την Θεωρία των Αποδείξεων,με την Αποτελεσματική Περιγραφική Θεωρία Συνόλων, την [[Θεωρία μοντέλων|ΘεωριαΘεωρία Μοντέλων]] και την Αφηρημένη Άλγεβρα. Μάλιστα, Θα μπορούσαμε να χαρακτηρίσουμε ότι η Θεωρία της Πολυπλοκότητας είναι γέννημα της Αναδρομικής Θεωρίας καθώς και οι δύο μοιράζονται ίδιο τεχνικό εργαλείο ,δηλαδή τη μηχανή Turing.
Οι θεωρητικοί της Αναδρομής στη μαθηματική λογική συχνά μελετούν τη θεωρία της σχετικής υπολογιστικότητας. Αυτό έρχεται σε αντίθεση με τη θεωρία της αναδρομικής ιεραρχίας, επίσημων μεθόδων και επίσημων γλωσσών, το οποίο είναι σύνηθες στην μελέτη της υπολογιστικής θεωρίας και της Πληροφορικής. Υπάρχει ένα αξιοσημείωτο κενό στις γνώσεις και στις μεθόδους μεταξύ των δύο ερευνητικών
κοινοτήτων, ωστόσο δεν μπορούν να διαχωριστούν εντελώς. Για παράδειγμα η παραμετρική πολυπλοκότητα, εφευρέθηκε από τον θεωρητικό της πολυπλοκότητας, Michael Fellows και τον θεωρητικό της αναδρομής Rod Downey.
 
Πίνακας περιεχομένων
1 Υπολογίσιμα και μη σύνολα
2 Αναδιαρθρωτική Υπολογισιμότητα
3 Πεδία Έρευνας
3.1 Σχετική υπολογίστικότητα και βαθμοί Turing
3.2 Άλλες Αναγωγισιμότητες
3.3 Το Θεώρημα του Rice και η Αριθμητική Ιεραρχία
3.4 Αντίστροφα Μαθηματικά
ιεραρχίας, επίσημων μεθόδων και επίσημων γλωσσών, το οποίο είναι σύνηθες στην μελέτη της υπολογιστικής θεωρίας και της Πληροφορικής. Υπάρχει ένα αξιοσημείωτο κενό στις γνώσεις και στις μεθόδους μεταξύ των δύο ερευνιτικών κοινοτήτων, ωστοσο δεν μπορούν να διαχωριστούν εντελώς. Για παράδειγμα η παραμετρική πολυπλοκότητα, εφευρέθηκε απο τον θεωρητικό της πολυπλοκότητας, Michael Fellows και τον θεωρητικό της αναδρομής Rod Downey.
 
 
 
Πίνακας περιεχομένων
1 Υπολογίσιμα και μη σύνολα
2 Αναδιαρθρωτική Υπολογισιμότητα
3 Πεδία Έρευνας
3.1 Σχετική υπολογίστικότητα και βαθμοί Turing
3.2 Άλλες Αναγωγισιμότητες
3.3 Το Θεώρημα του Rice και η Αριθμητική Ιεραρχία
3.4 Αντίστροφα Μαθηματικά
3.5 Αριθμήσεις
3.6 Η μέθοδος της Προτεραιότητας
3.7 Το δικτυωτό των Αναδρομικά Αριθμήσιμων Συνόλων
3.8 Προβλήματα Αυτομορφισμού
3.9 Πολυπλοκότητα του Kolmogorov
3.10 Υπολογισμός Συχνότητας
3.11 Επαγωγικά Συμπεράσματα
3.12 Γενικεύσεις της υπολογισιμότητας Turing
3.13 Συνεχής θεωρία υπολογισιμότητας
4 Σχέσεις μεταξύ Προσδιορισιμότητας και Υπολογισιμότητας
5 Όνομα του υποκειμένου
6 Επαγγελματικές οργανώσεις
7 Δείτε επίσης
8 Σημειώσεις
ιεραρχίας, επίσημων μεθόδων και επίσημων γλωσσών, το οποίο είναι σύνηθες στην μελέτη της υπολογιστικής θεωρίας και της Πληροφορικής. Υπάρχει ένα αξιοσημείωτο κενό στις γνώσεις και στις μεθόδους μεταξύ των δύο ερευνιτικών κοινοτήτων, ωστοσο δεν μπορούν να διαχωριστούν εντελώς. Για παράδειγμα η παραμετρική πολυπλοκότητα, εφευρέθηκε απο τον θεωρητικό της πολυπλοκότητας, Michael Fellows και τον θεωρητικό της αναδρομής Rod Downey.
 
 
 
Πίνακας περιεχομένων
1 Υπολογίσιμα και μη σύνολα
2 Αναδιαρθρωτική Υπολογισιμότητα
3 Πεδία Έρευνας
3.1 Σχετική υπολογίστικότητα και βαθμοί Turing
3.2 Άλλες Αναγωγισιμότητες
3.3 Το Θεώρημα του Rice και η Αριθμητική Ιεραρχία
3.4 Αντίστροφα Μαθηματικά
3.5 Αριθμήσεις
3.6 Η μέθοδος της Προτεραιότητας
3.7 Το δικτυωτό των Αναδρομικά Αριθμήσιμων Συνόλων
3.8 Προβλήματα Αυτομορφισμού
3.9 Πολυπλοκότητα του Kolmogorov
3.10 Υπολογισμός Συχνότητας
3.11 Επαγωγικά Συμπεράσματα
3.12 Γενικεύσεις της υπολογισιμότητας Turing
3.13 Συνεχής θεωρία υπολογισιμότητας
4 Σχέσεις μεταξύ Προσδιορισιμότητας και Υπολογισιμότητας
5 Όνομα του υποκειμένου
6 Επαγγελματικές οργανώσεις
7 Δείτε επίσης
8 Σημειώσεις
ιεραρχίας, επίσημων μεθόδων και επίσημων γλωσσών, το οποίο είναι σύνηθες στην μελέτη της υπολογιστικής θεωρίας και της Πληροφορικής. Υπάρχει ένα αξιοσημείωτο κενό στις γνώσεις και στις μεθόδους μεταξύ των δύο ερευνιτικών κοινοτήτων, ωστοσο δεν μπορούν να διαχωριστούν εντελώς. Για παράδειγμα η παραμετρική πολυπλοκότητα, εφευρέθηκε απο τον θεωρητικό της πολυπλοκότητας, Michael Fellows και τον θεωρητικό της αναδρομής Rod Downey.
 
 
 
Πίνακας περιεχομένων
Ανώνυμος χρήστης