On the Complexity of Computing Gödel Numbers
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Self-Supervised Evolution Operator Learning for High-Dimensional Dynamical Systems
auto-fpt: Automating Free Probability Theory Calculations for Machine Learning Theory
Double descent in quantum machine learning
Gradient Equilibrium in Online Learning: Theory and Applications
NLPrompt: Noise-Label Prompt Learning for Vision-Language Models
Federated Learning from Vision-Language Foundation Models: Theoretical Analysis and Method
토론
이 논문과 연결된 포럼 글이 아직 없습니다.