Dexter Kozen. Computational Inductive Definability. Annals of Pure and Applied Logic 126:1-3, April 2004, 139-148. Special issue: Provinces of logic determined. Essays in the memory of Alfred Tarski. Ed. Z. Adamowicz, S. Artemov, D. Niwinski, E. Orlowska, A. Romanowska, J. Wolenski.

It is shown that over any countable first-order structure, IND programs with dictionaries accept exactly the Pi-1-1 relations. This extends a result of Harel and Kozen (1984) relating IND and Pi-1-1 over countable structures with some coding power, and provides a computational analog of a result of Barwise, Gandy, and Moschovakis (1971) relating the Pi-1-1 relations on a countable structure to a certain family of inductively definable relations on the hereditarily finite sets over that structure.