Abstract
This paper studies the problem of learning computable functions in the limit by extending Gold's inductive inference framework to incorporate \textit{computational observations} and \textit{restricted input sources}. Complimentary to the traditional Input-Output Observations, we introduce Time-Bound Observations, and Policy-Trajectory Observations to study the learnability of general recursive functions under more realistic constraints. While input-output observations do not suffice for learning the class of general recursive functions in the limit, we overcome this learning barrier by imposing computational complexity constraints or supplementing with approximate time-bound observations. Further, we build a formal framework around observations of \textit{computational agents} and show that learning computable functions from policy trajectories reduces to learning rational functions from input and output, thereby revealing interesting connections to finite-state transducer inference. On the negative side, we show that computable or polynomial-mass characteristic sets cannot exist for the class of linear-time computable functions even for policy-trajectory observations.
Abstract (translated)
本文研究了通过扩展Gold的归纳推理框架来学习极限可计算函数的问题，该框架引入了\textit{计算观察}和\textit{受限输入源}。除了传统的输入-输出观察外，我们还提出了时间界限观察和策略轨迹观察，以在更现实的约束下研究通用递归函数的学习能力。虽然输入-输出观察不足以学习通用递归函数类在极限下的情况，但我们通过施加计算复杂性限制或补充近似的时间界限观察来克服这一学习障碍。此外，我们围绕\textit{计算代理}的观察构建了一个正式框架，并证明从策略轨迹中学习可计算函数可以转化为从输入和输出学习有理函数的问题，从而揭示了与有限状态转换器推理之间的有趣联系。另一方面，我们也展示了即使对于策略轨迹观察，线性时间可计算函数类也不能存在可计算或多项式质量特征集。
URL
https://arxiv.org/abs/2506.15543
