Supplement to Recursive Functions

Long descriptions for some figures in Recursive Functions

Figure 2 description

The Turing degrees \(\mathcal{D}_T\) figure consists of four black circles aligned vertically. The first and lowest is labeled “\(\mathbf{0}\) = degree of all computable sets”. The second is labeled “\(\mathbf{0}' = \textrm{deg}(K) = \textrm{deg}(\textit{HP})\)”. The third is labeled “\(\mathbf{0}'' = \textrm{deg}(\textit{TOT}) = \textrm{deg}(\textit{FIN}\))”. Between the third and fourth is a verticle ellipse. The fourth is labeled “ \(\mathbf{0}^{(n)}\)”. The first and second black circles are connected by two pairs of curved lines. The innermost pair is labeled “The c.e. degrees \(\mathcal{E}_T\)”. The outermost pair is labeled “Degrees \(a \le \mathbf{0}'\)”.

Figure 3 description

The Arithmetical Hierarchy figure is two vertical parallel lines each has five points with the bottommost one unlabeled; there is a vertical ellipse above the top. The left line’s labeled points are, from bottom to top, \(\Sigma^0_1\) through \(\Sigma^0_4\). The right line’s labeled points are, from bottom to top, \(\Pi^0_1\) through \(\Pi^0_4\). Eatch point on the left is connected to the points on the right that are above and below it (e.g., \(\Sigma^0_1\) is connected to the bottom unlabeled point on the right and to \(\Pi^0_2\)). Each of the intersections is also labeled and from bottom to top they are:

  • \(\Delta^0_1 = \textrm{computable sets}\) for the intersection of the lines from unlabeled to \(\Pi^0_1\) and from \(\Sigma^0_1\) to unlabeled.
  • \(\Delta^0_2 = \textrm{sets} \le_T \emptyset'\) for the intersection of the lines from \(\Sigma^0_1\) to \(\Pi^0_2\) and \(\Sigma^0_2\) to \(\Pi^0_1\)
  • \(\Delta^0_3 = \textrm{sets} \le_T \emptyset''\) for the intersection of the lines from \(\Sigma^0_2\) to \(\Pi^0_3\) and \(\Sigma^0_3\) to \(\Pi^0_2\)
  • \(\Delta^0_4 = \textrm{sets} \le_T \emptyset'''\) for the intersection of the lines from \(\Sigma^0_3\) to \(\Pi^0_4\) and \(\Sigma^0_4\) to \(\Pi^0_3\)

On the left line between the unlabeled bottom point and \(\Sigma^0_1\) is the label \(K \equiv_m \emptyset' =\) c.e. sets. Also on the left line between \(\Sigma^0_1\) and \(\Sigma^0_2\) is the label \(\textit{FIN} \equiv_m \emptyset''\).

On the right line between the unlabeled bottom point and \(\Pi^0_1\) is the label = co-c.e. sets \(\overline{K} \equiv_m \overline{\emptyset'}\). Also on the right line between \(\Pi^0_1\) and \(\Pi^0_2\) is the label \(\textit{TOT} \equiv_m \overline{\emptyset''}\).

Copyright © 2024 by
Walter Dean <W.H.Dean@warwick.ac.uk>
Alberto Naibo <alberto.naibo@univ-paris1.fr>

Open access to the SEP is made possible by a world-wide funding initiative.
The Encyclopedia Now Needs Your Support
Please Read How You Can Help Keep the Encyclopedia Free