Return to Answer

In general, the question of whether a given program $i$ is a fixed-point with respect to a given computuble function $f$, has complexity $\Pi^0_2$. And for some functions, it is $\Pi^0_2$-complete.

First, it is easy to see that the assertion that $i$ is a fixed point with respect to $f$, meaning that $\varphi_i=\varphi_{f(i)}$, has complexity at most $\Pi^0_2$, since $i$ is a fixed point just in case for every converging instance of one of the functions, there is a corresponding converging instance of the other with the same output value.

Conversely, let me provide a computable function $f$ for which the fixed-point set is $\Pi^0_2$-complete. Fix a $\Pi^0_2$-universal set $U$, where $x\in U$ if and only if $\forall k\ \exists j\ A(x,k,j)$, where $A$ is $\Delta_0$. Define $f$ as follows. For each $i$, let $f(i)$ be a program undertaking the following procedure: first, let $x=\varphi_i(0)$; now, on input $k$, search for $j$ for which $A(x,k,j)$, and output $x$ if found; otherwise keep searching.

For any $x$, let $e_x$ be a program that is known to compute constant value $x$. Observe that $x\in U$ just in case $f(e_x)$ computes the constant value $x$. Thus, $x\in U$ if and only if $e_x$ computes the same function as $f(e_x)$, which is to say, if and only if $e_x$ is a fixed point with respect to $f$.

So for this function, the fixed-point set is $\Pi^0_2$-complete. In particular, it is not c.e.

Update. Meanwhile, let us consider your updated question, focussed on the particular function $s(x)=x+1$. I claim that there is an admissible enumeration of computable functions for which the fixed-point question for this function is is not c.e. Suppose for example that we have an encoding where odd numbers always encode the empty function. (Many of the naturally occurring encodings of Turing machines or whatever have this property, if you use, say, prime powers for sequence encoding or $2^n(2m+1)$-type pairing functions, since odd numbers wouldn't code things as usual, and the corresponding enumerated computable function $\varphi_k$ for $k$ odd would be the empty function by default.) Thus, a fixed point $\varphi_e=\varphi_{e+1}$ for the successor function in this case would involve at least one odd index, and so it would be the empty function. Thus, an index $e$ is a fixed point if and only if $e$ is even and $\varphi_e$ is the empty function, or $e$ is odd and $\varphi_{e+1}$ is the empty function. This is easily seen to be co-c.e. and $\Pi^0_1$-complete, using methods as in my answer above. Basically, it is equivalent to the emptiness problem, which is $\Pi^0_1$-complete.

In general, the question of whether a given program $i$ is a fixed-point with respect to a given computuble function $f$, has complexity $\Pi^0_2$. And for some functions, it is $\Pi^0_2$-complete.

First, it is easy to see that the assertion that $i$ is a fixed point with respect to $f$, meaning that $\varphi_i=\varphi_{f(i)}$, has complexity at most $\Pi^0_2$, since $i$ is a fixed point just in case for every converging instance of one of the functions, there is a corresponding converging instance of the other with the same output value.

Conversely, let me provide a computable function $f$ for which the fixed-point set is $\Pi^0_2$-complete. Fix a $\Pi^0_2$-universal set $U$, where $x\in U$ if and only if $\forall k\ \exists j\ A(x,k,j)$, where $A$ is $\Delta_0$. Define $f$ as follows. For each $i$, let $f(i)$ be a program undertaking the following procedure: first, let $x=\varphi_i(0)$; now, on input $k$, search for $j$ for which $A(x,k,j)$, and output $x$ if found; otherwise keep searching.

For any $x$, let $e_x$ be a program that is known to compute constant value $x$. Observe that $x\in U$ just in case $f(e_x)$ computes the constant value $x$. Thus, $x\in U$ if and only if $e_x$ computes the same function as $f(e_x)$, which is to say, if and only if $e_x$ is a fixed point with respect to $f$.

So for this function, the fixed-point set is $\Pi^0_2$-complete. In particular, it is not c.e.

Update. Meanwhile, let us consider your updated question, focussed on the particular function $s(x)=x+1$. I claim that there is an admissible enumeration of computable functions for which the fixed-point question for this function is is not c.e. Suppose for example that we have an encoding where odd numbers always encode the empty function. (Many of the naturally occurring encodings of Turing machines or whatever have this property, if you use, say, prime powers for sequence encoding or $2^n(2m+1)$-type pairing functions, since odd numbers wouldn't code things as usual, and the corresponding enumerated computable function $\varphi_k$ for $k$ odd would be the empty function by default.) Thus, a fixed point $\varphi_e=\varphi_{e+1}$ for the successor function in this case would involve at least one odd index, and so it would be the empty function. Thus, an index $e$ is a fixed point if and only if $e$ is even and $\varphi_e$ is the empty function, or $e$ is odd and $\varphi_{e+1}$ is the empty function. This is easily seen to be co-c.e. and $\Pi^0_1$-complete, using methods as in my answer above. Basically, it is equivalent to the emptiness problem, which is $\Pi^0_1$-complete. In particular, it is not c.e.

In general, the question of whether a given program $i$ is a fixed-point with respect to a given computuble function $f$, has complexity $\Pi^0_2$. And for some functions, it is $\Pi^0_2$-complete.

First, it is easy to see that the assertion that $i$ is a fixed point with respect to $f$, meaning that $\varphi_i=\varphi_{f(i)}$, has complexity at most $\Pi^0_2$, since $i$ is a fixed point just in case for every converging instance of one of the functions, there is a corresponding converging instance of the other with the same output value.

Conversely, let me provide a computable function $f$ for which the fixed-point set is $\Pi^0_2$-complete. Fix a $\Pi^0_2$-universal set $U$, where $x\in U$ if and only if $\forall k\ \exists j\ A(x,k,j)$, where $A$ is $\Delta_0$. Define $f$ as follows. For each $i$, let $f(i)$ be a program undertaking the following procedure: first, let $x=\varphi_i(0)$; now, on input $k$, search for $j$ for which $A(x,k,j)$, and output $x$ if found; otherwise keep searching.

For any $x$, let $e_x$ be a program that is known to compute constant value $x$. Observe that $x\in U$ just in case $f(e_x)$ computes the constant value $x$. Thus, $x\in U$ if and only if $e_x$ computes the same function as $f(e_x)$, which is to say, if and only if $e_x$ is a fixed point with respect to $f$.

So for this function, the fixed-point set is $\Pi^0_2$-complete. In particular, it is not c.e.

In general, the question of whether a given program $i$ is a fixed-point with respect to a given computuble function $f$, has complexity $\Pi^0_2$. And for some functions, it is $\Pi^0_2$-complete.

First, it is easy to see that the assertion that $i$ is a fixed point with respect to $f$, meaning that $\varphi_i=\varphi_{f(i)}$, has complexity at most $\Pi^0_2$, since $i$ is a fixed point just in case for every converging instance of one of the functions, there is a corresponding converging instance of the other with the same output value.

Conversely, let me provide a computable function $f$ for which the fixed-point set is $\Pi^0_2$-complete. Fix a $\Pi^0_2$-universal set $U$, where $x\in U$ if and only if $\forall k\ \exists j\ A(x,k,j)$, where $A$ is $\Delta_0$. Define $f$ as follows. For each $i$, let $f(i)$ be a program undertaking the following procedure: first, let $x=\varphi_i(0)$; now, on input $k$, search for $j$ for which $A(x,k,j)$, and output $x$ if found; otherwise keep searching.

For any $x$, let $e_x$ be a program that is known to compute constant value $x$. Observe that $x\in U$ just in case $f(e_x)$ computes the constant value $x$. Thus, $x\in U$ if and only if $e_x$ computes the same function as $f(e_x)$, which is to say, if and only if $e_x$ is a fixed point with respect to $f$.

So for this function, the fixed-point set is $\Pi^0_2$-complete. In particular, it is not c.e.

Update. Meanwhile, let us consider your updated question, focussed on the particular function $s(x)=x+1$. I claim that there is an admissible enumeration of computable functions for which the fixed-point question for this function is is not c.e. Suppose for example that we have an encoding where odd numbers always encode the empty function. (Many of the naturally occurring encodings of Turing machines or whatever have this property, if you use, say, prime powers for sequence encoding or $2^n(2m+1)$-type pairing functions, since odd numbers wouldn't code things as usual, and the corresponding enumerated computable function $\varphi_k$ for $k$ odd would be the empty function by default.) Thus, a fixed point $\varphi_e=\varphi_{e+1}$ for the successor function in this case would involve at least one odd index, and so it would be the empty function. Thus, an index $e$ is a fixed point if and only if $e$ is even and $\varphi_e$ is the empty function, or $e$ is odd and $\varphi_{e+1}$ is the empty function. This is easily seen to be co-c.e. and $\Pi^0_1$-complete, using methods as in my answer above. Basically, it is equivalent to the emptiness problem, which is $\Pi^0_1$-complete.

In general, the question of whether a given program $i$ is a fixed-point with respect to a given computuble function $f$, has complexity $\Pi^0_2$. And for some functions, it is $\Pi^0_2$-complete.

First, it is easy to see that the assertion that $i$ is a fixed point with respect to $f$, meaning $\varphi_i=\varphi_{f(i)}$, has complexity at most $\Pi^0_2$, since $i$ is a fixed point just in case for every converging instance of one of the functions, there is a corresponding converging instance of the other with the same output value.

Conversely, let me provide a computable function $f$ for which the fixed-point set is $\Pi^0_2$-complete. Fix a $\Pi^0_2$-universal set $U$, where $x\in U(x)$ if and only if $\forall k\ \exists j\ A(x,k,j)$, where $A$ is $\Delta_0$. Define $f$ as follows. For each $i$, let $f(i)$ be a program undertaking the following procedure: first, let $x=\varphi_i(0)$; now, on input $k$, search for $j$ for which $A(x,k,j)$, and output $x$ if found; otherwise keep searching.

For any $x$, let $e_x$ be a program that is known to compute constant value $x$. Observe that $x\in U$ just in case $f(e_x)$ computes the constant value $x$. Thus, $x\in U$ if and only if $e_x$ computes the same function as $f(e_x)$, which is to say, if and only if $e_x$ is a fixed point with respect to $f$.

So for this function, the fixed-point set is $\Pi^0_2$-complete. In particular, it is not c.e.

In general, the question of whether a given program $i$ is a fixed-point with respect to a given computuble function $f$, has complexity $\Pi^0_2$. And for some functions, it is $\Pi^0_2$-complete.

First, it is easy to see that the assertion that $i$ is a fixed point with respect to $f$, meaning that $\varphi_i=\varphi_{f(i)}$, has complexity at most $\Pi^0_2$, since $i$ is a fixed point just in case for every converging instance of one of the functions, there is a corresponding converging instance of the other with the same output value.

Conversely, let me provide a computable function $f$ for which the fixed-point set is $\Pi^0_2$-complete. Fix a $\Pi^0_2$-universal set $U$, where $x\in U$ if and only if $\forall k\ \exists j\ A(x,k,j)$, where $A$ is $\Delta_0$. Define $f$ as follows. For each $i$, let $f(i)$ be a program undertaking the following procedure: first, let $x=\varphi_i(0)$; now, on input $k$, search for $j$ for which $A(x,k,j)$, and output $x$ if found; otherwise keep searching.

For any $x$, let $e_x$ be a program that is known to compute constant value $x$. Observe that $x\in U$ just in case $f(e_x)$ computes the constant value $x$. Thus, $x\in U$ if and only if $e_x$ computes the same function as $f(e_x)$, which is to say, if and only if $e_x$ is a fixed point with respect to $f$.

So for this function, the fixed-point set is $\Pi^0_2$-complete. In particular, it is not c.e.