Αναδρομικό σύνολο

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση
Διάγραμα που δείχνει τη σχέση των προβλημάτων απόφασης στην θεωρία υπολογισιμότιτας.

Στη θεωρία υπολογισιμότητας, ένα σύνολο από φυσικούς αριθμούς λέγεται αναδρομικό (recursive), υπολογίσιμο (computable), ή αποφασίσιμο/αποκρίσιμο (decidable), αν υπάρχει αλγόριθμος που τερματίζει σε πεπερασμένο χρόνο και απαντάει σωστά στο αν ένας δεδομένος αριθμός ανήκει στο σύνολο ή όχι. Ένα σύνολο που δεν είναι υπολογίσιμο λέγεται μη υπολογίσιμο (non-computable) ή μη αποφασίσιμο / αναποκρίσιμο (undecidable).

Μια γενικότερη κατηγορία συνόλων αποτελείται από τα αναδρομικά αριθμήσιμα σύνολα. Για τα σύνολα αυτά, απαιτείται μόνο να υπάρχει αλγόριθμος που αποκρίνεται σωστά όταν ένας αριθμός ανήκει στο σύνολο. Ο αλγόριθμος μπορεί να μην απαντήσει ποτέ για αριθμούς που δεν είναι στο σύνολο, αλλά αν δώσει απάντηση δεν θα είναι ποτέ η λάθος.

Τυπικός ορισμός[Επεξεργασία | επεξεργασία κώδικα]

Ένα υποσύνολο S των φυσικών αριθμών λέγεται αναδρομικό αν υπάρχει μια ολική υπολογίσιμη συνάρτηση τέτοια ώστε αν και αν . Με άλλα λόγια, το σύνολο S είναι αναδρομικό αν και μόνο αν η συνάρτηση δείκτη είναι υπολογίσιμη.

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

Ιδιότητες[Επεξεργασία | επεξεργασία κώδικα]

  • Αν το A είναι αναδρομικό σύνολο τότε το συμπλήρωμα του A είναι αναδρομικό σύνολο. Αν A και B είναι αναδρομικά σύνολα τότε AB, AB και η εικόνα του A × B υπό την συνάρτηση ζεύγους του Καντόρ, είναι αναδρομικά σύνολα.
  • Ένα σύνολο A είναι αναδρομικό αν και μόνο αν το A και το συμπλήρωμά του είναι και τα δύο αναδρομικά αριθμήσιμα. Η προεικόνα ενός αναδρομικού συνόλου υπό μια ολική υπολογίσιμη συνάρτηση είναι αναδρομικό σύνολο. Η εικόνα ενός υπολογίσιμου συνόλου μέσω μιας ολικής υπολογίσιμης αμφίεσης είναι υπολογίσιμη.
  • Ένα σύνολο είναι αναδρομικό αν και μόνο αν είναι στο επίπεδο της αριθμητικής ιεραρχίας.
  • Ένα σύνολο είναι αναδρομικό αν και μόνο αν είναι είτε το πεδίο τιμών μιας ασθενώς αύξουσας ολικής υπολογίσιμης συνάρτησης ή το κενό σύνολο. Η εικόνα ενός υπολογίσιμου συνόλου μέσω μιας ασθενώς αύξουσας ολικής υπολογίσιμης συνάρτησης είναι υπολογίσιμη.

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα recursive set της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).