Effectively minimizing effective fixed-points

Abstract:

This note answers an open problem posed by H. Rogers, Jr. on p. 202 of Theory of recursive functions and effective computability by proving the following invariant form of one of his results [op. cit., p. 200, Theorem XIV]: for any fixed-point function n there exists a recursive function g such that if z is an index of an effective operator $\Psi$, then $g(z)$ is also an index of $\Psi$, and $\hat n(g(z))$ is an index of the minimum fixed-point of $\Psi$ with respect to inclusion.