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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση

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

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

Εντελώς ανάλογα μια μερική συνάρτηση είναι κάτω ημι-υπολογίσιμη αν η  είναι άνω ημι-υπολογίσιμης ή ανάλογα αν υπάρχει μια υπολογίσιμη συνάρτηση τέτοια ώστε

Εάν μια μερική συνάρτηση είναι και άνω και κάτω ημι-υπολογίσιμη λέγεται υπολογίσιμη.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

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