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

καμία σύνοψη επεξεργασίας
 
===== '''Άλλες Αναγωγισιμότητες''' =====
Κύρια άρθρα: [[Μείωση (θεωρία αναδρομής)]]
 
Η εν εξελίξει τομέα της έρευνας στη θεωρία αναδρομής μελετά τις σχέσεις αναγωγισιμότητας πλην της αναγωγισιμότητας του Turing . Ο Post (1944) εισήγαγε αρκετές ισχυρές αναγωγισιμότητες, που ονομάστηκαν έτσι επειδή υπαινίσσονται τραπέζι αληθινής αναγωγισιμότητας. Μια μηχανή Turing για την εφαρμογή μιας ισχυρής αναγωγισιμότητας θα υπολογίσει μια συνολική συνάρτηση ανεξάρτητα από το με ποιο oracle παρουσιάζεται. Ασθενείς αναγωγές είναι εκείνες όπου η διαδικασία μείωσης δεν μπορεί να τερματιστεί για όλα τα σύνολα αριθμών. Η αναγωγή του Turing είναι ένα παράδειγμα.
Όπως τις:
 
===== '''<u>[[Μία προς μία αναγωγισιμότητα</u>''']] =====
Το Α είναι το ένα προς ένα αναγώγιμο (ή 1-αναγώγιμο) στο Β αν υπάρχει μια συνολική υπολογίσιμη [[Συνάρτηση|αμφιμονοσήμαντη συνάρτηση]] τέτοια ώστε κάθε n είναι στην Α αν και μόνο αν το f(n) είναι στο Β.
 
===== '''<u>[[Πολλές προς μία αναγωγισιμότητα</u>]]''' =====
Αυτό είναι ουσιαστικά η αναγωγή ένα προς ένα χωρίς τον περιορισμό ότι το f είναι αμφιμονοσήμαντο. Το Α είναι πολλοί προς ένα αναγώγιμο (ή m-αναγώγιμη) στο Β, αν υπάρχει μια συνολικά υπολογίσιμη συνάρτηση, έτσι ώστε κάθε n ανήκει στο A αν και μόνο αν το f(n) είναι στο Β.
 
===== '''<u>[[Αναγωγισιμότητα του Πίνακα Αληθείας</u>]]''' =====
Το Α είναι αληθινά αναγώγιμο σε πίνακα Β,αν το Α είναι αναγώγιμο κατά Turing στο Β μέσω της μηχανής Turing που υπολογίζει μια συνολική συνάρτηση. Λόγω του συμπαγούς του [[Χώρου Cantor|Cantor χώρου]] , αυτό είναι ισοδύναμο με το να πούμε ότι η μείωση παρουσιάζει έναν ενιαίο κατάλογο ερωτήσεων (εξαρτώμενο μόνο από την είσοδο) στο oracle ταυτόχρονα,και στη συνέχεια, έχοντας δει τις απαντήσεις τους είναι σε θέση να παράγει ένα αποτέλεσμα χωρίς να ζητήσει πρόσθετες ερωτήσεις,ανεξάρτητα με την απάντησης του oracle των αρχικών ερωτημάτων. Πολλές παραλλαγές του πίνακα αληθινής αναγωγής έχουν επίσης μελετηθεί.
 
 
===== '''Το Θεώρημα του Rice και η Αριθμητική Ιεραρχία''' =====
Ο Ράις έδειξε ότι για κάθε μη τετριμμένη κατηγορία C (η οποία περιέχει ορισμένα αλλά όχι όλα τα σύνολα) στο ενδεικτικό σύνολο E = {e: το e στο We είναι στο C} έχει την ιδιότητα ότι είτε το [[πρόβλημα τερματισμού]] ή το συμπλήρωμά της είναι πολλές -ένα αναγώγιμο στο E, δηλαδή, μπορεί να χαρτογραφηθούν με τη χρήση [[ αναγωγή |πολλών-μίας αναγωγής]] έως Ε (βλ. [[θεώρημα του Rice]] για περισσότερες λεπτομέρειες). Όμως,πολλά από αυτά τα ενδεικτικά σύνολα είναι ακόμη πιο περίπλοκα από ότι το πρόβλημα τερματισμού.Τα εν λόγω είδη συνόλων μπορούν να ταξινομηθούν χρησιμοποιώντας την [[αριθμητική ιεραρχία]]. Για παράδειγμα,το ενδεικτικό σύνολο FIN της τάξης όλων των πεπερασμένων συνόλων είναι στο επίπεδο Σ2 , το ενδεικτικό σύνολο REC της τάξης όλων των αναδρομικών συνόλων είναι στο επίπεδο Σ3,το ενδεικτικό σύνολο COFIN όλων των ομοτελικών συνόλων είναι επίσης στο επιπέδου Σ3 και το ενδεικτικό σύνολο COMP της κατηγορίας όλων των ολοκληρωμένων συνόλων Turing στο Σ4 .Αυτά τα επίπεδα ιεραρχίας ορίζονται επαγωγικά, Σn+1 και περιέχονται ακριβώς όλα τα σύνολα που είναι αναδρομικά αριθμήσιμα σε σχέση με το Σn.Το Σ1 περιέχει τα αναδρομικά αριθμήσιμα σύνολα.Τα ενδεικτικά σύνολα που δίνονται εδώ είναι πλήρεις ακόμη και για τα επίπεδά τους,δηλαδή όλα τα σύνολα σε αυτά τα επίπεδα μπορεί να είναι πολλά προς ένα αναγώγιμα στα ενδεικτικά δοσμένα σύνολα.
 
===== '''Αντίστροφα μαθηματικά''' =====
Υπάρχουν στενοί δεσμοί μεταξύ του βαθμού Turing ενός συνόλου φυσικών αριθμών και της δυσκολίας (απο πλευράς αριθμητικης ιεραρχίας) προσδιορισμού αυτού του συνόλου χρησιμοποιώντας [[Λογική πρώτου βαθμού|Λογική Πρώτου Βαθμού]].Αυτή η σχέση έγινε εφικτή με την βοήθεια του θεωρήματος του Post.Μία λιγότερο ακριβής απόδειξη παρουσιάστηκε απο τον [[Κουρτ Γκέντελ]] με τις αποδείξεις του στα θεωρήματα ολοκληρωσιμότητας και μη ολοκληρωσιμότητας.οι αποδείξεις του Γκέντελ εξηγούν ότι ένα σύνολο λογικών συνεπειών μίας δυναμικής Λογικής Πρώτου Βαθμού είναι ένα αναδρομικά αριθμήσιμο σύνολο και αν η θεωρία ειναι αρκετά ισχυρή τότε αυτό το σύνολο θα είναι μη υπολογίσιμο.Παρομοίως το Θεώρημα της μη-Προσδιορισιμότητας του Τάρσκι Similarly, Tarski's μπορεί να ερμηνευτεί τόσο από την άποψη της προσδιορισιμότητας όσο και της υπολογισιμότητας.
 
Η Θεωρία της Αναδρομής συνδεέται με την αριθμητικη δευτέρου τάξης, μια τυπική θεωρία των φυσικών αριθμών και συνόλων φυσικών αριθμών.Το γεγονός οτι κάποια σύνολα ειναι υπολογίσιμα και κάποια σχετικά υπολογίσιμα συχνά σημαίνει ότι αυτά τα σύνολα μπορούν να οριστούν σε πιο αδύναμα υποσυστήματα αριθμητικής δευτέρου τάξης.Το πρόγραμμα των αντίστροφων reverse mathematics χρησιμοποιεί αυτά τα υποσυστήματα για να μετρήσει την μη υπολογισιμότητα σε κάποια πολύ γνωστά μαθηματικά θεωρήματα . .Ο Simpson (1999) αναφέρεται σε πολλές πτυχές της αριθμητικής δεύτερης τάξης και reverse mathematics.
 
Ο κλάδος της Θεωρίας Αποδείξεων περιλαμβάνει την μελέτη της αριθμητικής δεύτερης ταξης και τα [[Αξιώματα Πεάνο]] όπως επίσης και τυπικές θεωρίες των φυσικών πιο αδύναμες από τα Αξιώματα Πεάνο.Μία μέθοδος κατηγοριοποιήσης της ισχύς αυτών των αδύναμων συστημάτων γίνεται με τον χαρακτηρισμό για ποιές υπολογίσμες συναρτήσεις το σύστημα μπορει να αποδειχθεί πλήρες(βλ. Fairtlough and Wainer (1998)).Για παράδειγμα ,στην θεμελιωδώς αναδρομική αριθμητική οποιαδήποτε συνάρτηση που ειναι πλήρης ειναι θεμελιωδώς αναδρομική ,ενώ τα Αξιώματα Πεάνο αποδεικνύουν ότι συναρτήσεις όπως η συνάρτηση του Ackermann ,οι οποίες δεν είναι θεμελιωδώς αναδρομικές ,είναι πλήρης,Επομένως δεν αποδεικνύεται για όλες τις πλήρης-υπολογίσιμες συναρτήσεις οτι ειναι πλήρης και στην Αριθμητική Πεάνο.Μάλιστα μία τέτοια συνάρτηση δίνεται απο το θεώρημα Goodstein.
Η κύρια επαγγελματική οργάνωση για τη θεωρία της αναδρομής είναι [[η Ένωση της Συμβολικής Λογικής]] , η οποία οργανώνει διάφορα ερευνητικά συνέδρια κάθε χρόνο. Η διεπιστημονική ερευνητική οργάνωση Υπολογισιμότητα στην Ευρώπη (CiE) διοργανώνει επίσης μια σειρά ετήσιων συνεδρίων. Το συνέδριο CiE 2012 ήταν η διάσκεψη εκατονταετίας Turing , που πραγματοποιήθηκε στο Cambridge, στο πλαίσιο του έτους Alan Turing.
 
= Δείτε επίσης =
* [[Αναδρομή (επιστήμη υπολογιστών)]]
* [[Λογική Υπολογισιμότητα]] 
* [[Transcomputational πρόβλημα]] 
 
= Σημειώσεις =
# Πολλά από αυτά τα θεμελιώδη έγγραφα συλλέγονται στο The Undecidable (1965) που εκδόθηκε από τον [[Martin Davis]].
# Το πλήρες χαρτί μπορεί επίσης να βρεθεί στις σελίδες 150ff (με σχολιασμό από τον Charles Parsons στο 144ff) σε Feferman et al. συντάκτες 1990 Kurt Gödel Τόμος ΙΙ Εκδόσεις 1938-1974, Oxford University Press, Νέα Υόρκη,  [[ISBN 978-0-19-514721-6]]. Και οι δύο έχουν τυπώσει την ακόλουθη υποσημείωση * στον όγκο Davis από τον Κουρτ Γκέντελ το 1965: "Για να είμαι πιο ακριβής: η λειτουργία των ακεραίων είναι υπολογίσιμη σε κάθε επίσημο σύστημα που περιέχει αριθμητική αν και μόνο αν είναι υπολογίσιμη στην αριθμητική, όπου η συνάρτηση f ονομάζεται υπολογίσιμη στο S αν υπάρχει σε ένα υπολογίσιμο S που αντιπροσωπεύει την f (σελ. 150).
# [[Διάσκεψη για τη Λογική, Υπολογισιμότητα και τυχαιότητα]], 10 - 13 Ιαν 2007.
# Η [[αρχική σελίδα]] του Andre Nies έχει μια λίστα από ανοικτά προβλήματα στην πολυπλοκότητα Kolmogorov.
# [[Μαθηματικές|Μαθηματικές αναζητήσεις]] για τους τίτλους όπως «υπολογίσιμα enumerable" και "c.e." δείχνουν ότι πολλές εργασίες έχουν δημοσιευθεί με αυτήν την ορολογία, καθώς και με την άλλη.
# Lance Fortnow, "[[Είναι Αναδρομική, Computable ή να αποφασισθεί;]]" 15.02.2004, πρόσβαση 09/01/2006.
# Stephen G. Simpson, "[[Τι είναι η θεωρία computability;]]" FOM κατάλογο ηλεκτρονικού ταχυδρομείου, 08.24.1998, 01.09.2006 πρόσβαση.
# Harvey Friedman, «[[η θεωρία Μετονομασία αναδρομής]]," λίστα email FOM, 08.28.1998, 01.09.2006 πρόσβαση.
== Βιβλιογραφία ==
; Προπτυχιακά Έντυπα
23

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