University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Degree spectra of computable functions on natural numbers with standard order

Degree spectra of computable functions on natural numbers with standard order

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2022 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity