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 , then is also an index of , and is an index of the minimum fixed-point of with respect to inclusion.
Retrieve articles in Proceedings of the American Mathematical Society with MSC: 02.70
Retrieve articles in all journals with MSC: 02.70
Keywords: Effective fixed-point, recursive function, standard enumeration
Article copyright: © Copyright 1971 American Mathematical Society