Learning-theoretic perspectives of acceptable numberings

Ganesh Baliga, Anil M. Shende

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)177-187
Number of pages11
JournalAnnals of Mathematics and Artificial Intelligence
Volume17
Issue number2
DOIs
StatePublished - Jan 1 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Learning-theoretic perspectives of acceptable numberings'. Together they form a unique fingerprint.

Cite this