In formal language theory and the theory of computation, index sets have a slightly different meaning. Say we are given some universal Turing Machine U, a Turing Machine capable of simulating the behavior of any other Turing Machine given the encoding of that TM on its input tape. Every such encoding is simply a string of symbols from the Turing machine's input alphabet, and every such encoding may be reduced to a number in a simple way, into the Turing machine's "Godel number", or (to use Turing's original terminology) its description number. An index set is defined as the set of all the description numbers corresponding to the Turing machines that compute some partial recursive function in a set of such functions.

Note that any index set must either be empty or infinite, as an infinite number of Turing machines exist that can compute a particular function (one merely need add an arbitrary number of useless states to any Turing machine that computes the function to see this). The index set consisting of all partial recursive functions is obviously recursively enumerable, but remarkably enough, by Rice's Theorem, all other nontrivial index sets are actually undecidable.