Computable set

Summary

A computable set, also called a recursive or decidable set, is a set of natural numbers for which an algorithm decides membership. The algorithm must halt on every input and answer yes or no correctly. Computable sets are exactly the sets whose characteristic function is a total computable function. They are the bottom level of the hierarchies of complexity of sets in computability theory.