On the Amount of Nonconstructivity in Learning Recursive Functions

Authors: Rūsiņš Freivalds1 and Thomas Zeugmann2

Source: Theory and Applications of Models of Computation,
8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011, Proceedings,

(Mitsunori Ogihara and Jun Tarui, Eds.), Lecture Notes in Computer Science 6648, pp. 332-343, Springer 2011.

Abstract. Nonconstructive proofs are a powerful mechanism in mathematics. Furthermore, nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lipton (1982) and Freivalds (2009). They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem.

In the present paper, the amount of nonconstructivity in learning of recursive functions is studied. Different learning types are compared with respect to the amount of nonconstructivity needed to learn the whole class of general recursive functions. Upper and lower bounds for the amount of nonconstructivity needed are proved.

Keywords: inductive inference, recursive functions, nonconstructivity

1 This research was performed while this author was visiting the Division of Computer Science at Hokkaido University. The research of the first author was supported by Grant No. 09.1570 from the Latvian Council of Science and by Project 2009/0216/1DP/ from the European Social Fund.
2 Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas under Grant No. 21013001.

©Copyright 2011, Springer

Valid HTML 4.1