On the complexity of learning programs

DOI10.1007/978-3-031-36978-0_14MaRDI QIDQ6149041zbMATH OpenOpenAlexFDO

Authors Vasco Brattka

Publication date 12 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.04213

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Abstract: Given a computable sequence of natural numbers, it is a natural task to find a G"odel number of a program that generates this sequence. It is easy to see that this problem is neither continuous nor computable. In algorithmic learning theory this problem is well studied from several perspectives and one question studied there is for which sequences this problem is at least learnable in the limit. Here we study the problem on all computable sequences and we classify the Weihrauch complexity of it. For this purpose we can, among other methods, utilize the amalgamation technique known from learning theory. As a benchmark for the classification we use closed and compact choice problems and their jumps on natural numbers, and we argue that these problems correspond to induction and boundedness principles, as they are known from the Kirby-Paris hierarchy in reverse mathematics. We provide a topological as well as a computability-theoretic classification, which reveal some significant differences.

Recommendations

• ON LEARNING LIMITING PROGRAMS
• Learnable Algorithm on the Continuum
• Learning and computing in the limit
• Learning theory in the arithmetic hierarchy
• scientific article; zbMATH DE number 1678394

Cites work

• A note on the diamond operator
• A topological view on algebraic computation models
• Algebraic properties of the first-order part of a problem
• Alien coding
• Classical recursion theory. Vol. II
• Closed choice and a uniform low basis theorem
• Effective Choice and Boundedness Principles in Computable Analysis
• scientific article; zbMATH DE number 3681743 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• scientific article; zbMATH DE number 3291139 (Why is no real title available?)
• Language identification in the limit
• Learning recursive functions: A survey
• On the algebraic structure of Weihrauch degrees
• On the information carried by programs about the objects they compute
• On the uniform computational content of Ramsey's theorem
• Reverse Mathematics
• Slicing the truth. On the computable and reverse mathematics of combinatorial principles
• Stashing and parallelization pentagons
• Subsystems of second order arithmetic
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• THE DISCONTINUITY PROBLEM
• Weihrauch Complexity in Computable Analysis

This page was built for publication: On the complexity of learning programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149041)