1
$\begingroup$

Let $\varphi_0,\varphi_1,\varphi_2,\dots$ be an acceptable programming system. A function $f$ is extensional if, for all $x$ and $y$, $\varphi_x=\varphi_y$ implies that $\varphi_{f(x)}=\varphi_{f(y)}$. Now, let $A$ and $B$ index sets such that $A\leq_{m}B$ ($A$ is many-one reducible to $B$). Is there an extensional function $f$ such that $f$ is an $m$-reduction from $A$ to $B$?

$\endgroup$

1 Answer 1

1
$\begingroup$

There is not always such an $f$. Here's a proof.

Let $A$ be the index set of programs computing the total function whose output is $0$ on every input. Let $g$ be the function which takes each $e$ to the program that outputs $e$ on input $0$ and diverges on all other inputs. Let $B$ be the set of programs which have the same behavior as some program in the image of $g$ on $A$. That is, $a$ is in $B$ if it is the code for a program which outputs some $e$ on input $0$ and diverges on all other inputs and $e$ is in $A$.

Note that $A$ is a $\Pi^0_2$-complete set. The idea now is that if there is an extensional many-one reduction from $A$ to $B$ then $A$ is $\Delta^0_2$.

Suppose $f$ is an extensional many-one reduction of $A$ to $B$. Since all programs in $A$ have the same behavior, $f$ must send $A$ to a set of programs in $B$ which all have the same behavior. And by our choice of $B$, that behavior has to be outputting some $e$ on input $0$ and diverging on all other inputs. But this means $A$ is equal to $\{a \mid \phi_{f(a)}(0)\downarrow = e\} \setminus \{a \mid \text{for some } n > 0, \phi_{f(a)}(n)\downarrow\}$. Since these are both r.e. sets, $A$ is the difference of two r.e. sets, hence $\Delta^0_2$. This contradicts the fact that $A$ is $\Pi^0_2$-complete.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.