Computational Inductive Definability
Journal Article - Open Access
Cornell University Ithaca United States
Pagination or Media Count:
It is shown that over any countable first-order structure, IND programs with dictionaries accept exactly the pi 11 relations. This extends a result of Harel and Kozen Inform. and Control 63 12 1984 118 relating IND and pi 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 pi 11 relations on a countable structure to a certain family of inductively denable relations on the hereditarily finite sets over that structure.
- Numerical Mathematics