Komputebla aro

Subaro S de la naturaj nombroj estas nomita kiel komputebla se ekzistas tuteca komputebla funkcio

${\displaystyle f:S\to \mathbb {N} }$

kun

${\displaystyle f(x)=\left\{{\begin{matrix}0&{\mbox{se}}\ x\in S\\\neq 0&{\mbox{se}}\ x\notin S\end{matrix}}\right.}$

En aliaj vortoj la aro S estas komputebla se kaj nur se la nadla funkcio ${\displaystyle 1_{S}}$ estas komputebla.

• Malplena aro
• Aro de naturaj nombroj
• Ĉiu finia subaro de aro de naturaj nombroj
• Aro de primoj
• Rekursia lingvo estas komputebla aro en aro de ĉiuj eblaj vortoj super la alfabeto de la formala lingvo.

Se A estas komputebla aro do la komplemento de A estas komputebla aro.Se A kaj B estas komputeblaj aroj do A ∩ B, A ∪ B kaj A × B estas komputeblaj aroj. Aro A estas komputebla aro se kaj nur se A kaj la komplemento de A estas rekursie numereblaj aroj. La rezulto de komputebla aro sub tuteca komputebla funkcio estas komputebla aro.

• Rekursie numerebla aro
• Rekursia funkcio