On recursive functions and regressive isols

Joseph Barback and William Jackson

Vol. 139 (1989), No. 2, 209–224

DOI: 10.2140/pjm.1989.139.209

Abstract

We are interested in regressive isols, recursive functions, and the extension to the isols of recursive functions. Our results in the paper were motivated by an interest to clarify the nature of the domain in the regressive isols of the Myhill-Nerode extension to the isols of a recursive function of one-variable.

In particular, if f is a recursive function, f_Λ the Myhill-Nerode extension of f to the isols, Λ the set of isols, and Λ_R the set of regressive isols, we give a characterization of the set

and then relate f_Λ(Domf_Λ) to α_R where α is the range of f and α_R = Λ_R ∩ α_Λ where α_Λ is the Nerode extension of α to the isols.

Mathematical Subject Classification 2000

Primary: 03D50

Milestones

Received: 3 November 1987

Revised: 11 July 1988

Published: 1 October 1989