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

Στη θεωρία υπολογισιμότητας, μία ημι-υπολογίσιμη συνάρτηση είναι μια μερική συνάρτηση $f:\mathbb {Q} \rightharpoonup \mathbb {R}$ που μπορεί να προσεγγιστεί είτε από πάνω είτε από κάτω από μια υπολογίσιμη συνάρτηση.

Πιο συγκεκριμένα μια μερική συνάρτηση $f:\mathbb {Q} \rightarrow \mathbb {R}$ είναι άνω ημι-υπολογίσιμη, που σημαίνει ότι μπορεί να προσεγγιστεί από πάνω, αν υπάρχει μια υπολογίσιμη συνάρτηση $\phi (x,k):\mathbb {Q} \times \mathbb {N} \rightharpoonup \mathbb {Q}$, όπου $x$ είναι η επιθυμητή παράμετρος, για την $f(x)$ και $k$ είναι το επίπεδο προσέγγισης, έτσι ώστε:

• $\lim _{k\rightarrow \infty }\phi (x,k)=f(x)$
• $\forall k\in \mathbb {N} :\phi (x,k+1)\leq \phi (x,k)$

Εντελώς ανάλογα μια μερική συνάρτηση $f:\mathbb {Q} \rightharpoonup \mathbb {R}$ είναι κάτω ημι-υπολογίσιμη αν η $-f(x)$ είναι άνω ημι-υπολογίσιμης ή ανάλογα αν υπάρχει μια υπολογίσιμη συνάρτηση $\phi (x,k)$ τέτοια ώστε

• $\lim _{k\rightarrow \infty }\phi (x,k)=f(x)$
• $\forall k\in \mathbb {N} :\phi (x,k+1)\geq \phi (x,k)$

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

Δείτε επίσης

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

Αναφορές

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