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

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

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

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

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

Ένα υποσύνολο S των φυσικών αριθμών λέγεται αναδρομικό αν υπάρχει μια ολική υπολογίσιμη συνάρτηση f\, τέτοια ώστε f(x) = 1\, αν x \in S και f(x) = 0\, αν x \notin S. Με άλλα λόγια, το σύνολο S είναι αναδρομικό αν και μόνο αν η συνάρτηση δείκτη 1_{S}\, είναι υπολογίσιμη.

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


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

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

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

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