# On the Complexity of Computing G"odel Numbers

arXiv: https://arxiv.org/abs/2302.04213 · HTML: https://mlsanity.com/paper/2302.04213/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 35 references that are in the map.
- First posted on arXiv 8 Feb 2023.

## Builds on (most cited first, 11 of 11)

- [Alien Coding](https://mlsanity.com/paper/2301.11479/) (2023)
- [Weihrauch Complexity in Computable Analysis](https://mlsanity.com/paper/1707.03202/) (2017)
- [On the Uniform Computational Content of Computability Theory](https://mlsanity.com/paper/1501.00433/) (2015)
- [A topological view on algebraic computation models](https://mlsanity.com/paper/1602.08004/) (2016)
- [On the algebraic structure of Weihrauch degrees](https://mlsanity.com/paper/1604.08348/) (2016)
- [A Galois connection between Turing jumps and limits](https://mlsanity.com/paper/1802.01355/) (2018)
- [Algebraic properties of the first-order part of a problem](https://mlsanity.com/paper/2203.16298/) (2022)
- [On the information carried by programs about the objects they compute](https://mlsanity.com/paper/1409.6977/) (2014)
- [On the Uniform Computational Content of the Baire Category Theorem](https://mlsanity.com/paper/1510.01913/) (2015)
- [Completion of Choice](https://mlsanity.com/paper/1910.13186/) (2019)
- [The Discontinuity Problem](https://mlsanity.com/paper/2012.02143/) (2020)

## Abstract (arXiv)

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.