Komputebla aro

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En komputebleca teorio kalkulebla aro estas nomita kiel komputebla, rekursiadecidebla se oni povas konstrui algoritmon kiu finiĝas post finia kvanto de tempo kaj decidas ĉu ĉiu donita ero apartenas al la aro aŭ ne.

Difino[redakti | redakti fonton]

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

f:S \to \mathbb{N}

kun

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 1_{S} estas komputebla.

Ekzemploj[redakti | redakti fonton]

Propraĵoj[redakti | redakti fonton]

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

Vidu ankaŭ[redakti | redakti fonton]