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

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

Στη θεωρία υπολογισιμότητας, ένα σύνολο από φυσικούς αριθμούς λέγεται **αναδρομικό** (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^0_1 της αριθμητικής ιεραρχίας.
* Ένα σύνολο είναι αναδρομικό αν και μόνο αν είναι είτε το πεδίο τιμών μιας ασθενώς αύξουσας ολικής υπολογίσιμης συνάρτησης ή το κενό σύνολο. Η εικόνα ενός υπολογίσιμου συνόλου μέσω μιας ασθενώς αύξουσας ολικής υπολογίσιμης συνάρτησης είναι υπολογίσιμη.

## Αναφορές
* Μοσχοβάκης Γ. Ν. *[https://web.archive.org/web/20131107023401/http://www.math.ucla.edu/~ynm/lectures/nirt.pdf Αναδρομή και υπολογισιμότητα]*, 2011
* Τζουβάρας Αθ. *[https://web.archive.org/web/20130903101248/http://users.auth.gr/tzouvara/Texfiles.htm/TRF.pdf Θεωρία αναδρομικών συναρτήσεων και υπολογισιμότητας]*, διδακτικές σημειώσεις, Θεσσαλονίκη 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

Κατηγορία:Θεωρία υπολογισμού
Κατηγορία:Μαθηματική λογική