Degree spectra of computable functions on natural numbers with standard order

Add to your list(s) Download to your calendar using vCal

• Dariusz Kalociński (Polish Academy of Sciences)
• Friday 10 June 2022, 11:15-12:15
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact nobody.

SASW09 - International conference on computability, complexity and randomness

The degree spectrum of a computable relation on a computable structure consists of all Turing degrees of the images of the relation across all computable copies of the structure. Investigation of the degree spectra of computable relations on the computable structure consisting of natural numbers and the standard order has exhibited spectra such as the trivial one, all c.e. degrees and all degrees. I will review recent results regarding the restriction of this problem to graphs of unary total recursive functions. This approach has led, among others, to the the negative answer to one of the questions posed by M. Wright, namely whether the aforementioned spectra exhaust all possibilities. The talk will be based on a joint work with N. Bazhenov and M. Wrocławski.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.