A class of recursive functions C is limiting standardizable, in a programming system ψ, iff there is an effective procedure which, given any ψ-program (in the ψ-system), synthesizes in the limit a canonical ψ-program which is equivalent to the former. It can arguably be expected that notions similar to the above one would be relevant to Gold-style function learning, which features, among other things, the effective limiting synthesis of programs for input recursive functions. Many learning classes have been characterized in terms of variants of the above notion. In this paper, we focus on the limiting standardizability of the entire class of recursive functions in effective programming systems. To start with, we prove the independence of this notion vis-à-vis finitary recursion theorems. Secondly, we show that this notion does not entail acceptability, in the spirit of the results of Case, Riccardi and Royer on characterizations of the same vis-à-vis programming language control structures.
All Science Journal Classification (ASJC) codes
- Artificial Intelligence
- Applied Mathematics