Ημι-υπολογίσιμη συνάρτηση

Στη θεωρία υπολογισιμότητας, μία ημι-υπολογίσιμη συνάρτηση είναι μια μερική συνάρτηση  που μπορεί να προσεγγιστεί είτε από πάνω είτε από κάτω από μια υπολογίσιμη συνάρτηση.

Πιο συγκεκριμένα μια μερική συνάρτηση  είναι άνω ημι-υπολογίσιμη, που σημαίνει ότι μπορεί να προσεγγιστεί από πάνω, αν υπάρχει μια υπολογίσιμη συνάρτηση , όπου  είναι η επιθυμητή παράμετρος, για την  και  είναι το επίπεδο προσέγγισης, έτσι ώστε:
 
 
Εντελώς ανάλογα μια μερική συνάρτηση  είναι κάτω ημι-υπολογίσιμη αν η  είναι άνω ημι-υπολογίσιμης ή ανάλογα αν υπάρχει μια υπολογίσιμη συνάρτηση  τέτοια ώστε
 
 
Εάν μια μερική συνάρτηση είναι και άνω και κάτω ημι-υπολογίσιμη λέγεται υπολογίσιμη.

Δείτε επίσης 
 θεωρία υπολογισιμότητας

Αναφορές 
 Μινγκ Λι και ο Παύλος Vitányi, Μια Εισαγωγή στην Πολυπλοκότητα Kolmogorov και Τις Εφαρμογές της, pp 37–38, Springer, 1997.

Μαθηματική λογική