Komputebla aro

En komputebleca teorio kalkulebla aro nomiĝas komputebla, rekursia aŭ decidebla, se ekzistas algoritmo, kies plenumado finiĝas post finia nombro da paŝoj per decido, ĉu donita ero apartenas al tiu aro aŭ ne.

Difino

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

kun

En aliaj vortoj la aro S estas komputebla se kaj nur se la nadla funkcio  estas komputebla.

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.

Propraĵoj

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.

 Vidu ankaŭ 

Rekursie numerebla aro
Rekursia funkcio

Kategorio:Rekursia teorio
Kategorio:Aro-teorio