BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Vasco Brattka (Bundeswehr München) DTSTART:20230614T090000Z DTEND:20230614T100000Z DTSTAMP:20260423T035420Z UID:CompAlg/17 DESCRIPTION:Title: On the Complexity of Computing Gödel Numbers\nby Vasco Brattka (Bund eswehr München) as part of Machine Learning Seminar\n\n\nAbstract\nGiven a computable sequence of natural numbers\, it is a natural task to find a Gödel number of a program that generates this sequence. It is easy to see that this problem is neither continuous nor computable. In algorithmic le arning theory this problem is well studied from several perspectives and o ne question studied there is for which sequences this problem is at least learnable in the limit. Here we study the problem on all computable sequen ces and we classify the Weihrauch complexity of it. For this purpose we ca n\, among other methods\, utilize the amalgamation technique known from le arning theory. As a benchmark for the classification we use closed and com pact choice problems and their jumps on natural numbers\, and we argue tha t these problems correspond to induction and boundedness principles\, as t hey are known from the Kirby-Paris hierarchy in reverse mathematics. We pr ovide a topological as well as a computability-theoretic classification\, which reveal some significant differences.\n LOCATION:https://researchseminars.org/talk/CompAlg/17/ END:VEVENT END:VCALENDAR