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

μ
μ
== Υπολογίσιμα και μη υπολογίσιμα σύνολα ==
 
Η Αναδρομή θεωρία προέρχεται από τη δεκαετία του 1930, με το έργο του [[Kurt Gödel ]], [[Alonzo Church ]], [[Alan Turing ]], [[Στίβεν Κλέινι|Stephen Kleene]] και [[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) καλύπτει πολλά από τα γνωστά αποτελέσματα σε αυτόν τον τομέα.
 
=== Σχετική Υπολογισιμότητα και Βαθμός Turing ===
Η θεωρία της αναδρομής στη Μαθηματική λογική παραδοσιακά εστιαζόταν στη σχετική υπολογισιμότητα, μια γενίκευση της υπολογισιμότητας Turing, που καθορίζεται χρησιμοποιώντας μια [[μηχανή Turing]] που παρουσιάστηκε από τον Turing (1939). Μια μηχανή χρησμού Turing, είναι μία υποθετική συσκευή, η οποία εκτός από τις παραδοσιακές ενέργειες μιας μηχανής Turing, μπορεί να κάνει ερωτήσεις για ένα συγκεκριμένο σύνολο ακέραιων αριθμών. Η μηχανή oracle μπορεί να κάνει ερωτήσεις της μορφής «Είναι το n στο σύνολο oracle;» Κάθε ερώτηση θα απαντάται άμεσα σωστά ακόμη και αν το σύνολο δεν είναι υπολογίσιμο.
 
Ανεπίσημα, ένα σύνολο ακεραίων αριθμών Α είναι [[αναγώγιμο]] σε ένα σύνολο Β αν υπάρχει μια μηχανή oracle που σωστά εάν οι αριθμοί είναι στο Α όταν εκτελούνται με το Β, όπως στο σύνολο oracle (σε αυτή την περίπτωση, το σύνολο Α επίσης λέγεται ότι είναι (σχετικά) υπολογίσιμο από το Β και το Β μπορεί να αναχθεί στο Α τότε το σύνολο λέγεται ότι έχουν τον ίδιο [[βαθμός Turing|βαθμό Turing]] (ονομάζεται επίσης βαθμός unsolvability). [[Ο βαθμός Turing]] ενός συνόλου δίνει ένα ακριβές μέτρο του πόσο μη-υπολογίσιμο είναι το σύνολο.
5.211

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