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 [] and Freivalds []. 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.M., Blum, M.: Inductive inference and unsolvability. The Journal of Symbolic Logic 56(3), 891–900 (1991)
Bārzdiņš, J.M.: Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set. Soviet Mathematics Doklady 9, 1251–1254 (1968)
Blum, M.: A machine independent theory of the complexity of recursive functions. Journal of the ACM 14(2), 322–336 (1967)
Case, J., Smith, C.: Comparison of identification criteria for machine inductive inference. Theoretical Computer Science 25(2), 193–220 (1983)
Cholak, P., Downey, R., Fortnow, L., Gasarch, W., Kinber, E., Kummer, M., Kurtz, S., Slaman, T.A.: Degrees of inferability. In: Proc. 5th Annual ACM Workshop on Computational Learning Theory, pp. 180–192. ACM Press, New York (1992)
Damm, C., Holzer, M.: Automata that take advice. In: Hájek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol. 969, pp. 149–158. Springer, Heidelberg (1995)
Erdős, P.: Some remarks on the theory of graphs. Bulletin of the American Mathematical Society 53(4), 292–294 (1947)
Freivald, R.V., Wiehagen, R.: Inductive inference with additional information. Elektronische Informationsverarbeitung und Kybernetik 15(4), 179–185 (1979)
Freivald, R.: Minimal gödel numbers and their identification in the limit. In: Bečvář, J. (ed.) MFCS 1975. LNCS, vol. 32, pp. 219–225. Springer, Heidelberg (1975)
Freivalds, R.: Inductive inference of recursive functions: Qualitative theory. In: Bārzdiņš, J., Bjørner, D. (eds.) Baltic Computer Science. LNCS, vol. 502, pp. 77–110. Springer, Heidelberg (1991)
Freivalds, R.: Amount of nonconstructivity in finite automata. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol. 5642, pp. 227–236. Springer, Heidelberg (2009)
Freivalds, R.: Amount of nonconstructivity in deterministic finite automata. Theoretical Computer Science 411(38-39), 3436–3443 (2010)
Gold, E.M.: Limiting recursion. The Journal of Symbolic Logic 30, 28–48 (1965)
Gold, E.M.: Language identification in the limit. Inform. Control 10(5), 447–474 (1967)
Jain, S., Osherson, D., Royer, J.S., Sharma, A.: Systems that Learn: An Introduction to Learning Theory, 2nd edn. MIT Press, Cambridge (1999)
Kalmár, L.: On the reduction of the decision problem. First Paper. Ackermann prefix, a single binary predicate. The Journal of Symbolic Logic 4(1), 1–9 (1939)
Karp, R.M., Lipton, R.J.: Turing machines that take advice. L’ Enseignement Mathématique 28, 191–209 (1982)
КинϬер, Е.Б.: О лредельном синтезе почти минимальных геделевских номеров. In: Bārzdiņš, J. (ed.) Теория Алгоритмов и Программ, vol. I, pp. 212–223. Latvian State University (1974)
Kummer, M., Stephan, F.: On the structure of the degrees of inferability. Journal of Computer and System Sciences 52(2), 214–238 (1996)
Landweber, L.H., Robertson, E.L.: Recursive properties of abstract complexity classes. Journal of the ACM 19(2), 296–308 (1972)
Pepis, J.: Ein Verfahren der mathematischen Logik. The Journal of Symbolic Logic 3(2), 61–76 (1938)
Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967); reprinted, MIT Press (1987)
Trakhtenbrot, B.A., Barzdin, Y.M.: Finite Automata, Behavior and Synthesis. North Holland, Amsterdam (1973)
Wiehagen, R.: Zur Theorie der Algorithmischen Erkennung. Dissertation B, Humboldt-Universität zu Berlin (1978)
Zeugmann, T., Zilles, S.: Learning recursive functions: A survey. Theoretical Computer Science 397(1-3), 4–56 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Freivalds, R., Zeugmann, T. (2011). On the Amount of Nonconstructivity in Learning Recursive Functions. In: Ogihara, M., Tarui, J. (eds) Theory and Applications of Models of Computation. TAMC 2011. Lecture Notes in Computer Science, vol 6648. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20877-5_33
Download citation
DOI: https://doi.org/10.1007/978-3-642-20877-5_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20876-8
Online ISBN: 978-3-642-20877-5
eBook Packages: Computer ScienceComputer Science (R0)