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

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

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

• $\underset{k\to \mathrm{\infty }}{\lim }\varphi (x,k)=f(x)$
• $\mathrm{\forall }k\in \mathbb{N}:\varphi (x,k+1)\le \varphi (x,k)$

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

• $\underset{k\to \mathrm{\infty }}{\lim }\varphi (x,k)=f(x)$
• $\mathrm{\forall }k\in \mathbb{N}:\varphi (x,k+1)\ge \varphi (x,k)$

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

Δείτε επίσης

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

Αναφορές

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