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

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας
Ετικέτα: μεγάλη προσθήκη
Χωρίς σύνοψη επεξεργασίας
Γραμμή 100:
 
 
*=== Το δικτυωτό των Αναδρομικά Αριθμήσιμων Συνόλων ===
Όταν ο Post όρισε την έννοια ενός απλού συνόλου, ως ενός εκ νέου συνόλου με ένα άπειρο συμπλήρωμα που δεν περιέχει κανένα άπειρο σύνολο re, άρχισε τη μελέτη της δομής των αναδρομικά αριθμήσιμων συνόλων υπό ένταξη. Αυτό το πλέγμα έγινε μια καλά μελετημένη δομή. Αναδρομικά σύνολα μπορούν να οριστούν σε αυτή τη δομή από τη βασικό αποτέλεσμα ότι ένα σύνολο είναι αναδρομικό αν και μόνο αν το σύνολο και το συμπλήρωμά του είναι αναδρομικά αριθμήσιμα. Άπειρα σύνολα έχουν πάντα άπειρα αναδρομικά υποσύνολα αλλά από την άλλη πλευρά, υπάρχουν απλά σύνολα που υπάρχουν, αλλά δεν έχουν αναδρομικό υπερσύνολο. Ο Post (1944) εισήγαγε ήδη υπεραπλά και υπερυπεραπλά σύνολα. Αργότερα μέγιστα σύνολα κατασκευάστηκαν τα οποία είναι σύνολα τέτοια ώστε κάθε υπερσύνολο είναι είτε ένα πεπερασμένο παραλλαγή του συγκεκριμένου μέγιστου συνόλου ή συν-πεπερασμένο. Το αρχικό κίνητρο του Post στη μελέτη αυτού του πλέγματος ήταν να βρεθεί μια δομική αντίληψη, έτσι ώστε κάθε σύνολο που ικανοποιεί αυτή την ιδιότητα δεν είναι ούτε στο βαθμό Turing των αναδρομικών συνόλων ούτε στο βαθμό Turing του προβλήματος τερματισμού. Ο Post δεν κατάφερε να βρει τον εν λόγω κώδικα και η λύση στο πρόβλημά του εφαρμόστηκε στις μεθόδους προτεραιότητας. Ο Harrington και ο Soare (1991), βρήκαν τελικά ένα τέτοιο κώδικα.
* Προβλήματα Αυτομορφισμού