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

μ
καμία σύνοψη επεξεργασίας
μ (Διόρθωση επικεφαλίδων.)
μ
Η Θεωρία της Αναδρομής συνδεέται με την [[αριθμητική δευτέρου τάξης]], μια τυπική θεωρία των φυσικών αριθμών και συνόλων φυσικών αριθμών.Το γεγονός οτι κάποια σύνολα ειναι υπολογίσιμα και κάποια σχετικά υπολογίσιμα συχνά σημαίνει ότι αυτά τα σύνολα μπορούν να οριστούν σε πιο αδύναμα υποσυστήματα αριθμητικής δευτέρου τάξης.Το πρόγραμμα των [[αντίστροφων μαθηματικών]] χρησιμοποιεί αυτά τα υποσυστήματα για να μετρήσει την μη υπολογισιμότητα σε κάποια πολύ γνωστά μαθηματικά θεωρήματα. Ο Simpson (1999) αναφέρεται σε πολλές πτυχές της αριθμητικής δεύτερης τάξης και reverse mathematics.
 
Ο κλάδος της [[Θεωρίας Αποδείξεων]] περιλαμβάνει την μελέτη της αριθμητικής δεύτερης ταξης και τα [[Αξιώματα Πεάνο]] όπως επίσης και τυπικές θεωρίες των φυσικών πιο αδύναμες από τα Αξιώματα Πεάνο.Μία μέθοδος κατηγοριοποιήσης της ισχύς αυτών των αδύναμων συστημάτων γίνεται με τον χαρακτηρισμό για ποιέςποιες υπολογίσμες συναρτήσεις το σύστημα μπορει να αποδειχθεί [[πλήρες]](βλ. Fairtlough and Wainer (1998)).Για παράδειγμα ,στην [[θεμελιωδώς αναδρομική αριθμητική]] οποιαδήποτε συνάρτηση που ειναι πλήρης ειναι [[θεμελιωδώς αναδρομική]] ,ενώ τα [[Αξιώματα Πεάνο]] αποδεικνύουν ότι συναρτήσεις όπως η [[συνάρτηση του Ackermann]] ,οι οποίες δεν είναι θεμελιωδώς αναδρομικές ,είναι πλήρης,Επομένως δεν αποδεικνύεται για όλες τις πλήρης-υπολογίσιμες συναρτήσεις οτι ειναι πλήρης και στην Αριθμητική Πεάνο.Μάλιστα μία τέτοια συνάρτηση δίνεται απο το θεώρημα Goodstein.
 
== Όνομα του Υποκειμένου ==
82.768

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