• Calendar

November 7, Wednesday
12:00 – 14:00

A function is Turing computable if it can be specified by a Turing machine. Turing's definition [1936] of a function, computable by a Turing machine, was followed in his dissertation [1939], in which he defined the notion of a set $A$ being computable relative to a set $B$. We then say $A$ is Turing reducible to $B$ ($A\leq_T B$). We identify a degree as an equivalence class of sets of natural numbers, each reducible to the other

The least degree is the set of all recursive subsets of $\omega$, denoted $\deg{0}$. A degree $\deg{b}$ is minimal if $\deg{b}>\deg{0}$ and there is no $\deg{c}$ such that $\deg{0}<\deg{c}<\deg{b}$. That is, it is minimal in the ordering of degrees. I will present Spector's result [1956]: There is a minimal degree. It follows that the ordering $\leq$ on $\D$ (the structure of the degrees) is not dense. This result proved to be useful in many embedability results as well as other results concerning the structure of $\D$.