UTM theorem

The theorem states that a partial computable function u of two variables exists such that, for every computable function f of one variable, a number e exists such that f(x) \simeq u(e,x) for all x. This means that, for each x, either f(x) and u(e,x) are both defined and are equal, or are both undefined. The theorem thus shows that, defining φe(x) as u(e, x), the sequence φ1, φ2, ... is an enumeration (numbering) of the partial computable functions. In fact, u can be chosen so this is the standard numbering. The function u in the statement of the theorem is called a universal function. == References ==