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

καμία σύνοψη επεξεργασίας
Οι θεωρητικοί της Αναδρομής στη μαθηματική λογική συχνά μελετούν τη θεωρία της σχετικής υπολογιστικότητας. Αυτό έρχεται σε αντίθεση με τη θεωρία της αναδρομικής ιεραρχίας, επίσημων μεθόδων και επίσημων γλωσσών, το οποίο είναι σύνηθες στην μελέτη της υπολογιστικής θεωρίας και της Πληροφορικής. Υπάρχει ένα αξιοσημείωτο κενό στις γνώσεις και στις μεθόδους μεταξύ των δύο ερευνιτικών
κοινοτήτων, ωστοσο δεν μπορούν να διαχωριστούν εντελώς. Για παράδειγμα η παραμετρική πολυπλοκότητα, εφευρέθηκε απο τον θεωρητικό της πολυπλοκότητας, 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''' Σημειώσεις
 
'''9''' Αναφορές
 
'''10''' Επιπλέον Σύνδεσμοι
 
Υπολογίσιμα και μη υπολογίσιμα σύνολα.
Πολλά προβλήματα των μαθηματικών έχει αποδειχθεί ότι είναι άλυτα αφού αυτά τα αρχικά παραδείγματα καθιερώθηκαν. Το 1947, ο Markov και ο Post δημοσίευσαν ανεξάρτητες μελέτες που δείχνουν ότι η λέξη πρόβλημα για υποσύνολα δεν μπορεί να λυθεί αποτελεσματικά. Επεκτείνοντας αυτό το αποτέλεσμα, ο Pyotr Novikov και ο William Boone έδειξαν ανεξάρτητα στη δεκαετία του 1950 ότι η λέξη πρόβλημα για τις ομάδες δεν είναι αποτελεσματικά επιλύσιμο: δεν υπάρχει αποτελεσματική διαδικασία η οποία, δοσμένης μιας λέξης σε μια παρουσιασμένη ομάδα , θα αποφασίσει εάν το στοιχείο που αντιπροσωπεύεται από τη λέξη είναι το στοιχείο της ταυτότητας της ομάδας. Το 1970, ο Yuri Matiyasevich αποδείχθηκε (χρησιμοποιώντας τα αποτελέσματα της Julia Robinson ) το Matiyasevich θεώρημα του , πράγμα που σημαίνει ότι το δέκατο πρόβλημα του Hilbert 's δεν έχει καμία αποτελεσματική λύση. Το πρόβλημα αυτό ρώτησε αν υπάρχει μια αποτελεσματική διαδικασία για να αποφασιστεί εάν μια εξίσωση Diophantine επί των ακεραίων έχει μια λύση στα ακέραιοι. Ο κατάλογος των μη λυμένων προβλημάτων παρέχει επιπλέον παραδείγματα των προβλημάτων χωρίς υπολογίσιμη λύση.
Η μελέτη για το ποιες μαθηματικές κατασκευές μπορούν να πραγματοποιηθούν αποτελεσματικά μερικές φορές ονομάζεται αναδρομικά μαθηματικά. Το Εγχειρίδιο των Αναδρομικών Μαθηματικών (Ershov et al. 1998) καλύπτει πολλά από τα γνωστά αποτελέσματα σε αυτόν τον τομέα.
 
 
 
===== '''Πεδία Έρευνας''' =====
23

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