En komputebleca teorio kalkulebla aro nomiĝas komputebla, rekursiadecidebla, 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 redakti

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 redakti

Propraĵoj redakti

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 numereblaj aroj. La rezulto de komputebla aro sub tuteca komputebla funkcio estas komputebla aro.

Vidu ankaŭ redakti