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

Διάγραμα που δείχνει τη σχέση των προβλημάτων απόφασης στην θεωρία υπολογισιμότιτας.

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

Τυπικός ορισμός

Επεξεργασία

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

Παραδείγματα

Επεξεργασία

Ιδιότητες

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

Αναφορές

Επεξεργασία