Komputebla aro

El Vikipedio

En komputebleca teorio numerebla 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.

Enhavo

[redaktu] Difino

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

[redaktu] Ekzemploj

  • 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.

[redaktu] Propraĵoj

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.

[redaktu] Vidu ankaŭ jenon:

  • Rekursie numerebla aro
  • Rekursia funkcio