for each
, we define
it may also be written as
, see standard numbering of turing programs.
one of the key tools in computability theory is
for each
, the function
is partially computable.
(taken from Martin Davis, Ron Sigal, Elaine J. Weyuker, 1994 chapter 4.3 universality)