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

Στη θεωρία υπολογισιμότητας, ένα σύνολο από φυσικούς αριθμούς λέγεται αναδρομικό (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 είναι αναδρομικά σύνολα τότε A ∩ B, A ∪ B και η εικόνα του A × B υπό την συνάρτηση ζεύγους του Καντόρ, είναι αναδρομικά σύνολα.
• Ένα σύνολο A είναι αναδρομικό αν και μόνο αν το A και το συμπλήρωμά του είναι και τα δύο αναδρομικά αριθμήσιμα. Η προεικόνα ενός αναδρομικού συνόλου υπό μια ολική υπολογίσιμη συνάρτηση είναι αναδρομικό σύνολο. Η εικόνα ενός υπολογίσιμου συνόλου μέσω μιας ολικής υπολογίσιμης αμφίεσης είναι υπολογίσιμη.
• Ένα σύνολο είναι αναδρομικό αν και μόνο αν είναι στο επίπεδο $\Delta _{1}^{0}$ της αριθμητικής ιεραρχίας.
• Ένα σύνολο είναι αναδρομικό αν και μόνο αν είναι είτε το πεδίο τιμών μιας ασθενώς αύξουσας ολικής υπολογίσιμης συνάρτησης ή το κενό σύνολο. Η εικόνα ενός υπολογίσιμου συνόλου μέσω μιας ασθενώς αύξουσας ολικής υπολογίσιμης συνάρτησης είναι υπολογίσιμη.

Αναφορές

• Μοσχοβάκης Γ. Ν. Αναδρομή και υπολογισιμότητα, 2011
• Τζουβάρας Αθ. Θεωρία αναδρομικών συναρτήσεων και υπολογισιμότητας, διδακτικές σημειώσεις, Θεσσαλονίκη 2007
• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7