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

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

Στη θεωρία υπολογισιμότητας, ένα σύνολο από φυσικούς αριθμούς λέγεται αναδρομικό (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 και το συμπλήρωμά του είναι και τα δύο αναδρομικά αριθμήσιμα. Η προεικόνα ενός αναδρομικού συνόλου υπό μια ολική υπολογίσιμη συνάρτηση είναι αναδρομικό σύνολο. Η εικόνα ενός υπολογίσιμου συνόλου μέσω μιας ολικής υπολογίσιμης αμφίεσης είναι υπολογίσιμη.
• Ένα σύνολο είναι αναδρομικό αν και μόνο αν είναι στο επίπεδο ${\mathrm{\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