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

καμία σύνοψη επεξεργασίας
Η '''Θεωρία της Υπολογισιμότητας''' ή '''Θεωρία της Αναδρομής''', είναι ένας κλάδος της [[μαθηματική λογική|μαθηματικής λογικής]], της [[πληροφορική]]<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 Machine.
 
"Ο Tarski τόνισε στην ομιλία του (και νομίζω δικαίως) τη μεγάλη σημασία της έννοιας της γενικής αναδρομής (ή του υπολογιστικού περιβάλλοντος του Turing). Μου φαίνεται ότι η σημασία αυτή σε μεγάλο βαθμό οφείλεται στο γεγονός ότι με αυτήν την έννοια για πρώτη φορά κατόρθωσε κάποιος να δώσει μια απόλυτη έννοια σε μια ενδιαφέρουσα επιστημολογική αντίληψη, δηλαδή χωρίς να εξαρτάται από τον φορμαλισμό που επιλέγεται. (Gοdel 1946 στο Davis 1965:84).
Με τον ορισμό του αποτελεσματικού υπολογισμού ήρθαν οι πρώτοι αποδείξεις ότι υπάρχουν προβλήματα στα μαθηματικά που δεν μπορούν να αποφασιστούν αποτελεσματικά . Ο Chyrch (1936a, 1936b) και ο Turing (1936), εμπνευσμένοι από τεχνικές που χρησιμοποιούνται από τον Γκέντελ (1931) για να αποδείξουν τη μη πληρότητα των θεωρημάτων του , ανεξάρτητα κατέδειξαν ότι το Entscheidungs πρόβλημα δεν λύνεται αποτελεσματικά. Το αποτέλεσμα έδειξε ότι δεν υπάρχει αλγοριθμική διαδικασία που μπορεί σωστά να αποφασίσει αν κάποια αυθαίρετη μαθηματική πρόταση είναι αληθής ή ψευδής.
 
Πολλά προβλήματα των μαθηματικών έχει αποδειχθεί ότι είναι άλυτα αφού αυτά τα αρχικά παραδείγματα καθιερώθηκαν. Το 1947, ο Markov και ο Post δημοσίευσαν ανεξάρτητες μελέτες που δείχνουν ότι η λέξη πρόβλημα για υποσύνολα δεν μπορεί να λυθεί αποτελεσματικά. Επεκτείνοντας αυτό το αποτέλεσμα, ο Pyotr Novikov και ο William Boone έδειξαν ανεξάρτητα στη δεκαετία του 1950 ότι η λέξη πρόβλημα για τις ομάδες δεν είναι αποτελεσματικά επιλύσιμο: δεν υπάρχει αποτελεσματική διαδικασία η οποία, δοσμένης μιας λέξης σε μια παρουσιασμένη ομάδα , θα αποφασίσει εάν το στοιχείο που αντιπροσωπεύεται από τη λέξη είναι το στοιχείο της ταυτότητας της ομάδας. Το 1970, ο Yuri Matiyasevich αποδείχθηκε (χρησιμοποιώντας τα αποτελέσματα της Julia Robinson ) το Matiyasevich θεώρημα του , πράγμα που σημαίνει ότι το δέκατο πρόβλημα του Hilbert 's δεν έχει καμία αποτελεσματική λύση. Το πρόβλημα αυτό ρώτησε αν υπάρχει μια αποτελεσματική διαδικασία για να αποφασιστεί εάν μια εξίσωση Diophantine επί των ακεραίων έχει μια λύση στα ακέραιοι. Ο κατάλογος των μη λυμένων προβλημάτων παρέχει επιπλέον παραδείγματα των προβλημάτων χωρίς υπολογίσιμη λύση.
Η μελέτη για το ποιες μαθηματικές κατασκευές μπορούν να πραγματοποιηθούν αποτελεσματικά μερικές φορές ονομάζεται αναδρομικά μαθηματικά. Το Εγχειρίδιο των Αναδρομικών Μαθηματικών (Ershov et al. 1998) καλύπτει πολλά από τα γνωστά αποτελέσματα σε αυτόν τον τομέα.
 
 
 
28

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