there is no effective procedure for deciding, given any
, whether or not
is a total function. that is to say, there is no recursive function
such that
is not recursively enumerable.
consider the following reduction function:
, where:
then we have
which gives us the reduction
.