Funkcja półobliczalna

W teorii obliczalności funkcja półobliczalna jest $pomocą$ częściową , przybliżyć z góry lub z dołu funkcji .

Dokładniej, $, że$ częściowa jest górna semicomputable , co ${\ Displaystyle \ phi (x, k): \ mathbb {Q} \ razy \ mathbb {N} \ rightarrow \ mathbb {Q}} , gdzie$ , jeśli istnieje funkcja obliczalna x $\ Displaystyle x}$ jest pożądane parametr dla ${\ Displaystyle f (x)}$ i ${\ Displaystyle k}$ to poziom przybliżenia taki, że:

• ${\ Displaystyle \ lim _ {k \ strzałka w prawo \ infty} \ phi (x, k) = f (x)}$
• ${\ Displaystyle \ forall k \ in \ mathbb {N}: \ phi (x, k + 1) \ równoważnik \ phi (x, k)}$

$jest$ analogiczna funkcja częściowa niższa półobliczalna i tylko wtedy, gdy - $}$ górna półobliczalna lub równoważnie, jeśli istnieje funkcja obliczalna taka, że ${\ Displaystyle \ phi (x, k)}$

• ${\ Displaystyle \ lim _ {k \ strzałka w prawo \ infty} \ phi (x, k) = f (x)}$
• ${\ Displaystyle \ forall k \ in \ mathbb {N}: \ phi (x, k + 1) \ geq \ phi (x, k)}$

Jeśli funkcja częściowa jest zarówno górna, jak i dolna półobliczalna , nazywa się ją obliczalną.

Zobacz też

• Teoria obliczalności

• Ming Li i Paul Vitányi, Wprowadzenie do złożoności Kołmogorowa i jej zastosowań , s. 37–38, Springer, 1997.