Computational inductive definability Original Research Article

It is shown that over any countable first-order structure, IND programs with dictionaries accept exactly the Π11 relations. This extends a result of Harel and Kozen (Inform. and Control 63 (1–2) (1984) 118) relating IND and Π11 over countable structures with some coding power, and provides a computational analog of a result of Barwise et al. (J. Symbolic Logic 36 (1971) 108) relating the Π11 relations on a countable structure to a certain family of inductively definable relations on the hereditarily finite sets over that structure.