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

Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση
μ
Διόρθωση συντακτικών λαθών του κώδικα με τη χρήση AWB (11457)
μ
μ (Διόρθωση συντακτικών λαθών του κώδικα με τη χρήση AWB (11457))
== Υπολογίσιμα και μη υπολογίσιμα σύνολα ==
 
Η Αναδρομή θεωρία προέρχεται από τη δεκαετία του 1930, με το έργο του [[Kurt Gödel , Alonzo Church , Alan Turing , Stephen Kleene]] και[[Emil Post| Emil Post.]].
 
Τα θεμελιώδη αποτελέσματα που αποκόμισαν οι ερευνητές εγκαθίδρυσαν την [[αναδιαρθρωτική υπολογισιμότητα]] ως σωστή επισημοποίησης της άτυπης ιδέα του αποτελεσματικού υπολογισμού. Αυτά τα αποτελέσματα οδήγησαν τον [[Stephen Kleene]] (1952) για να πλάσει τα δύο ονόματα "Church's thesis" (Kleene 1952:300) και «Turing's Thesis» (Kleene 1952:376). Σήμερα αυτά συχνά θεωρούνται ως μια ενιαία υπόθεση η [[Church–Turing|Church–Turing thesis]] η οποία ορίζει ότι κάθε [[λειτουργία]] που είναι [[ υπολογίσιμη]] από τον [[αλγόριθμο]] είναι μια υπολογίσιμη συνάρτηση . Αν και αρχικά σκεπτικός, από το 1946 ο Gödel τάχθηκε υπέρ αυτής της διατριβής:
 
: «Ο 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|Yuri Matiyasevich ]]<nowiki/>αποδείχθηκε (χρησιμοποιώντας τα αποτελέσματα της [[Julia Robinson]] ) το [[Matiyasevich θεώρημα]] του , πράγμα που σημαίνει ότι [[το δέκατο πρόβλημα του Hilbert]] δεν έχει καμία αποτελεσματική λύση. Το πρόβλημα αυτό ρώτησε αν υπάρχει μια αποτελεσματική διαδικασία για να αποφασιστεί εάν μια [[εξίσωση Diophantine]] επί των ακεραίων έχει μια λύση στα ακέραιοι. [[Ο κατάλογος των μη|Ο κατάλογος των μη λυμένων προβλημάτων]] παρέχει επιπλέον παραδείγματα των προβλημάτων χωρίς υπολογίσιμη λύση.
 
Η μελέτη για το ποιες μαθηματικές κατασκευές μπορούν να πραγματοποιηθούν αποτελεσματικά μερικές φορές ονομάζεται '''αναδρομικά μαθηματικά'''. Το Εγχειρίδιο των Αναδρομικών Μαθηματικών (Ershov et al. 1998) καλύπτει πολλά από τα γνωστά αποτελέσματα σε αυτόν τον τομέα.
Τα φυσικά παραδείγματα των συνόλων που δεν είναι υπολογίσιμα, συμπεριλαμβανομένων πολλών διαφορετικών συνόλων που κωδικοποιούν παραλλαγές του [[πρόβλημα τερματισμού|προβλήματος τερματισμού]], έχουν δύο κοινές ιδιότητες:
 
#Είναι [[ αναδρομικά αριθμήσιμα]], και
#Κάθε ένα μπορεί να μεταφραστεί σε οποιοδήποτε άλλο μέσω [[πολλών-μίας μείωσης]]. Δηλαδή, δεδομένων τέτοιων συνόλων Α και Β, υπάρχει μία συνολική λειτουργία τέτοια ώστε Α={x:f(x)∈B} Αυτά τα σύνολα λέγεται ότι είναι πολλές-ένα ισοδύναμο (ή m-ισοδύναμο).
 
 
=== Το Θεώρημα του Rice και η Αριθμητική Ιεραρχία ===
Ο Ράις έδειξε ότι για κάθε μη τετριμμένη κατηγορία C (η οποία περιέχει ορισμένα αλλά όχι όλα τα σύνολα) στο ενδεικτικό σύνολο E = {e: το e στο We είναι στο C} έχει την ιδιότητα ότι είτε το [[πρόβλημα τερματισμού]] ή το συμπλήρωμά της είναι πολλές -ένα αναγώγιμο στο E, δηλαδή, μπορεί να χαρτογραφηθούν με τη χρήση [[ αναγωγή |πολλών-μίας αναγωγής]] έως Ε (βλ. [[θεώρημα του Rice]] για περισσότερες λεπτομέρειες). Όμως,πολλά από αυτά τα ενδεικτικά σύνολα είναι ακόμη πιο περίπλοκα από ότι το πρόβλημα τερματισμού.Τα εν λόγω είδη συνόλων μπορούν να ταξινομηθούν χρησιμοποιώντας την [[αριθμητική ιεραρχία]]. Για παράδειγμα,το ενδεικτικό σύνολο FIN της τάξης όλων των πεπερασμένων συνόλων είναι στο επίπεδο Σ2 , το ενδεικτικό σύνολο REC της τάξης όλων των αναδρομικών συνόλων είναι στο επίπεδο Σ3,το ενδεικτικό σύνολο COFIN όλων των ομοτελικών συνόλων είναι επίσης στο επιπέδου Σ3 και το ενδεικτικό σύνολο COMP της κατηγορίας όλων των ολοκληρωμένων συνόλων Turing στο Σ4 .Αυτά τα επίπεδα ιεραρχίας ορίζονται επαγωγικά, Σn+1 και περιέχονται ακριβώς όλα τα σύνολα που είναι αναδρομικά αριθμήσιμα σε σχέση με το Σn.Το Σ1 περιέχει τα αναδρομικά αριθμήσιμα σύνολα.Τα ενδεικτικά σύνολα που δίνονται εδώ είναι πλήρεις ακόμη και για τα επίπεδά τους,δηλαδή όλα τα σύνολα σε αυτά τα επίπεδα μπορεί να είναι πολλά προς ένα αναγώγιμα στα ενδεικτικά δοσμένα σύνολα.
 
=== Αντίστροφα μαθηματικά ===
 
=== Αρίθμηση ===
Η αρίθμηση είναι μια απαρίθμηση των συναρτήσεων.Έχει δύο παραμέτρους,e και χ και εξάγει την τιμή της συνάρτησης e στην αρίθμηση για την είσοδο x. Οι αριθμήσεις μπορεί να είναι μερικά-αναγώγιμες αν και ορισμένα από τα μέλη τους είναι συνολικά αναγώγιμα, δηλαδή, υπολογίσιμες συναρτήσεις.[[Παραδεκτές αριθμήσεις]] είναι εκείνες στις οποίες όλες οι άλλες μπορούν να μεταφραστούν.Μια[[Friedberg| αρίθμηση Friedberg]] (που ονομάζεται από αυτόν που την ανακάλυψε)είναι η ένα προς ένα αρίθμηση όλων των επιμέρους-αναδρομικών συναρτήσεων,είναι κατ 'ανάγκην μια μη παραδεκτή αρίθμηση.Μεταγενέστερη έρευνα ασχολήθηκε επίσης με αριθμήσεις από άλλες κατηγορίες όπως τις τάξεις των αναδρομικά αριθμήσιμων συνόλων. Ο Goncharov ανακάλυψε για παράδειγμα μια κατηγορία αναδρομικά αριθμήσιμων συνόλων για τα οποία οι αριθμήσεις εμπίπτουν σε δύο κατηγορίες ακριβώς σε σχέση με τους αναδρομικούς ισομορφισμούς.
 
=== Η μέθοδος της Προτεραιότητας ===
 
== Οι Επαγγελματικές Οργανώσεις ==
Η κύρια επαγγελματική οργάνωση για τη θεωρία της αναδρομής είναι [[η Ένωση της Συμβολικής Λογικής]] , η οποία οργανώνει διάφορα ερευνητικά συνέδρια κάθε χρόνο. Η διεπιστημονική ερευνητική οργάνωση [[Υπολογισιμότητα στην Ευρώπη]] (CiE) διοργανώνει επίσης μια σειρά ετήσιων συνεδρίων. Το συνέδριο CiE 2012 ήταν η διάσκεψη εκατονταετίας [[Turing]] , που πραγματοποιήθηκε στο Cambridge, στο πλαίσιο του [[έτους Alan Turing|έτους Alan Turing.]].
 
== Σημειώσεις ==
16.024

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

Μενού πλοήγησης