Universiteit van Amsterdam

News item

Institute for Logic, Language and Computation

News and Events: 11 September 2012, Logic Tea, Zhenhao Li

Please note that this newsitem has been archived, and may contain outdated information or links.

Speaker: Zhenhao Li
Title: Computable Functionals on the Countable Ordinals
Date and time: Tuesday 11 September 2012, 17:00-18:00
Location: Room A1.04, Science Park 904, Amsterdam

Countable ordinals can be represented by well orderings on subsets of natural numbers. Fixing a computable pairing function, each well ordering on a subset of natural numbers can be coded into a set of natural numbers which is called a "real code". We say that a (partial) function $f$ on the countable ordinals is computable if there is an oracle Turing machine such that given any real code $X$ of any ordinal $\alpha$ in the domain of $f$ as the oracle it will "output" a real code of $f(\alpha)$. In other words, $f$ is computable if real codes of $f(\alpha)$ are computable uniformly from real codes of $\alpha$ for any $\alpha$ in the domain of $f$. We show that the three basic operations of ordinal arithmetic are computable. We study other "natural" functions and show that some are computable and some are not.

We define that $\alpha$ is reducible to $\beta$ if the singleton function $(\beta, \alpha)$ is computable. This induces a degree structure on the countable ordinals, where the bottom degree is the set of computable ordinals. We show that the order type of the degree of $\omega_1^{ck}$ is at least $\omega$ which is a consequence of among others the statement that the singleton function $(\omega_1^{ck}+\omega, \omega_1^{ck})$ is computable.

The Logic Tea homepage can be found at http://www.illc.uva.nl/logic_tea/ For more information, please contact Johannes Marti (johannes.marti at gmail.com), Sebastian Speitel (sebastian.speitel at gmail.com), or Matthijs Westera (M.Westera at uva.nl).

The websites of the UvA make use of cookies. More information Hide this message X