% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}

\def\R{{\mathbb R}}
\def\cc{{\mathfrak c}}
\def\res{{\upharpoonright}}

\def\om{\omega}
\def\lec#1{{\par\bigskip\noindent (#1)\par}}

\newcount\probno
\probno=0
\def\prob{\advance\probno by 1 \par\bigskip\par\noindent
\kern-10pt \the\probno . }

\begin{document}
\begin{flushright}
  A.Miller \\
  M773       \\
  Computability Theory\\
  Fall 2001
\end{flushright}


\lec{9-5} Def Turing machine, Turing computable functions.

\lec{9-7} Def Primitive recursive functions, Primitive recursive implies
Turing computable.
\prob Prove $f(n)=2n$ is Turing computable by constructing an actual
Turing machine.

\lec{9-10} Def Partial recursive functions, Partial recursive implies
Turing computable. Started on converse.
\prob Define $n$ is square-free iff $n\geq 2$ and no $m^2$ divides $n$
for $m\geq 2$.  Let $S(n)$ be the sum of the first $n$ square-free
numbers.  Prove $S$ is a Primitive recursive function.

\lec{9-12} For any partial Turing computable  $f$ there exists
primitive recursive $g$ and $R$ such that
$$f(\vec{n})=g(\mu x\; R(x,\vec{n}))$$
\prob Prove there is a total $f:\om\to\om$ such that
the graph of $f$ is a primitive recursive predicate but $f$
is not primitive recursive.

\lec{9-17}
Church-Turing Thesis, universal functions, halting problem,
effective listing of all primitive recursive functions,
a computable function which is not primitive recursive.
\prob Prove that the halting problems for nonwritting Turing
machines is decidable.  A Turing machine m is nonwritting
iff whenever $m(s,a)=(s',a',d)$ then $a=a'$.
It is decidable whether or not $m$ halts when given
input $x=<x_1,\ldots,x_n>\in A^n$ started on $x_1$ in state $s_0$.

\newpage
\lec{9-19}
Padding Lemma, S-n-m Theorem,
\par\noindent computably enumerable=range
of computable function = $\Sigma^0_1$,
\par\noindent computable=ce and co-ce, K not computable.
\prob Show there exists a uniformly computable listing of
all partial computable functions,
$\{\psi_e(x):e\in \omega\}$, which fails the padding lemma.
Hint: Obtain a listing so that the empty function only
occurs once, say as $\psi_0$.

\lec{9-21}
every infinite ce set contains an infinite comp set, every inf
ce set has a 1-1 enumeration,
many-one reducibility, one-reducibility, K, W one-complete.
\prob (a) Prove that every nonempty computably enumerable set
has a primitive recursive enumeration.
\par *(b) Prove or disprove: Every infinite computably enumerable set
has a one-one primitive recursive enumeration.

\lec{9-24}
(Myhill) 1-1 equivalence iff computable permutation, (Rogers) if $\psi_e$
unif enum of partial comp fcns
satisfies padding, s-1-1, then there is a comp permutation $\pi$ with
$\psi_e=\phi_{\pi(e)}$ all $e$. Rice's index theorem.
\prob In Roger's Theorem prove that s-1-1 implies padding.
Hint: Soare I-5.9.

\lec{9-26}
Post's construction of a simple set, (Myhill) 1-1 equivalence to K
is the same as creative.

\prob Define $V_e=\{n: <e,n>\in V\}$. Prove or disprove:
\par (a) $\exists V$ c.e. such $\{V_e:e\in\omega\}$ is the set of
all computable sets.
\par (b) $\exists V$ computable such $\{V_e:e\in\omega\}$ is the set of
all computable sets.
\par (c) $\exists V$ c.e. such $\{V_e:e\in\omega\}$ is the set of
all nonempty c.e. sets.
\par (d) $\exists f$ computable function such that for all $e\;\;$
$W_e\not=\emptyset$ implies $f(e)\in W_e$.
\par (e) $\exists f$ partial computable such that for all $e\;\;$
$W_e\not=\emptyset$ implies $f(e)\downarrow\in W_e$.


\lec{9-28}
Recursion Theorem, uniform recursion theorem, recursion theorem with
parameters.

\prob Prove
\par (a) $\exists^\infty e\;\; W_e=\{0,1,2,\ldots,e\}$
\par (b) Suppose $V\subseteq \omega$ is c.e.
$\exists^\infty e\;\; W_e=V_e$ (where $V_e=\{n:<e,n>\in V\}$)
\par (c) there exists $e_1,e_2$ with $e_1\not=e_2$ and
$W_{e_1}=\{e_2\}$ and $W_{e_2}=\{e_1\}$

\lec{10-1} Def Turing reducible,
Dekker deficiency set is simple and Turing equivalent to the set.
\prob Computable Skolem functions?  Prove or disprove:
\par (a) Given a computable $R\subseteq\omega^2$ such that
$\forall x\exists y \;R(x,y)$ there exists a computable $f$
such that $\forall x\;R(x,f(x))$
\par (b) Given a computable $R\subseteq\omega^3$ such that
$\forall x\exists y \forall z\;R(x,y,z)$ there exists a computable $f$
such that $\forall x\forall z\;R(x,f(x),z)$
\par Hint: Think "Simple".

\lec{10-3} (Martin) $A$ effectively simple implies $A\equiv_T K$.
Def $A\oplus B$, $A'$.
\prob Prove
\par (a) $A\leq_T A\oplus B$ and $B\leq_T A\oplus B$
\par (b) $A\oplus B\equiv_T B\oplus A$
\par (c) $(A\oplus B)\oplus C\equiv_T A\oplus (B\oplus C)$
\par (d) if $A\leq_T C$ and $B\leq_T C$, then $A\oplus B\leq_T C$
\par (e) if $A\leq_T \hat{A}$ and $B\leq_T \hat{B}$, then
$A\oplus B\leq_T \hat{A}\oplus \hat{B}$

\lec{10-5}
Def Turing jump, $A\equiv_T B$ implies $A'\equiv_T B'$, (Kleene-Post)
there exists incomparable Turing degrees.

\lec{10-8}
Kleene-Post. For every $a>0$ there exists  $b$ incomparable to $a$.
There exists $a,b$ nonzero with infimum 0.
\prob Prove
\par (a) there exists $A$ such that for every $n$
\par\noindent $A_n$ is not Turing reducible to $\cup\{A_m: m\not=n\}$
\par (b) There exists Turing degrees $a_r$ for $r\in {\mathbf Q}$
such that
\par\noindent for all $r,s\in {\mathbf Q}\;\;$
($r<s$ iff $a_r < a_s$).   Hint: use part (a).
\par (c)* Same as part (b) but also $a_r<0'$ for all $r$.

\lec{10-10}
(Kleene-Post-Spector) Given increasing degrees $\langle a_n:n\in\omega
\rangle$ there are upper bounds $b,c$ such that $d\leq b$ and $d\leq c$
implie for some $n$ that $d\leq a_n$.

\prob Show that for every nonzero degree $a$ there is a no zero $b$
such that $0$ is the infimum of $a$ and $b$.
\prob Show that $0^{(\omega)}$ is not a minimal upper bound of
$\{0^{(n)}:n\in\omega\}$.
\par Hint: in theorem above get $B,C$ computable in $0^{(\omega)}$.

\lec{10-12}
(Friedberg) For every $B\geq_T 0'$ there exists
$A$ with $A'\equiv_TB$.
\prob Prove there exists a degree $a>0$ with $a'=0'$.

\lec{10-15}
(Spector) minimal degrees exist. (Sacks) minimal upper bounds exist.
\prob Prove there exists a perfect tree $T$ such that every
branch thru $T$ has minimal degree.

\lec{10-17}
Def $\Sigma_n^0$ etc., simple closure properties, universal $\Sigma_n^0$
sets, limit lemma.
\prob Find the natural arithmetic classes in which the following sets
belong:
\par (a) $\{e: W_e=\emptyset\}$
\par (b) $\{e: W_e$ is simple $\}$
\par (c) $\{e: W_e\equiv_T K\}$
\par (d) $\{<e_1,e_2> : W_{e_1}=^* W_{e_2}\}$ (equal mod finite)

\lec{10-19}
$\forall^\infty=\exists\forall$, $A'\in\Sigma_1^0(A)$,
$A\leq_T 0^{(n)}$ iff $A\in\Delta_{n+1}^0$, $0^{(n)}\in \Sigma^0_n$,
FIN $\Sigma_2^0$-complete
\prob Prove that $A$ is $\Sigma^0_4$ iff there exists a computable
$P(s,t,x)$ such that for every $x$
$$A(x)\equiv \forall^\infty s\;\forall^\infty t\; P(s,t,x)$$

\lec{10-22}
TOT is $\Pi^0_2$-complete, REC is $\Sigma^0_3$-complete.
\prob Prove there is {\bf no} $\Delta_2^0$-complete set $A$
(i.e. $A$ is $\Delta_2^0$ and every $\Delta_2^0$ is many-one reducible
to $A$)
\par Hint: Consider $B=\{e:\varphi_e(e)\downarrow$ and
$\varphi_e(e)\notin A\}$.

\prob Prove of disprove:
\par (a) there exists a total $f\leq_T 0''$ such that for all
$e$, if $W_e$ is computable, then $W_{f(e)}=\overline{W_e}$.
\par (b) there exists a total $f\leq_T 0^{(3)}$ such that for all
$e$, if $W_e$ is computable, then $W_{f(e)}=\overline{W_e}$.


\lec{10-24}
COF is complete $\Sigma^0_3$, $\exists\forall\exists=\forall^\infty\exists$,
started first priority argument: low simple set.

\lec{10-26}
(Friedberg-Muchnik) There are Turing incomparable c.e. sets.
\prob Prove that SIMP$=\{\;e:W_e$ is simple$\}$ is a complete
$\Pi^0_3$ set.
\par Hint: Like the proof for COF but also let $W_e$ kick the $e^{th}$ marker
at most once to make $A$ meet $W_e$ if $W_e$ infinite.

\lec{10-29}
Every countable poset embedds into the computably enumerable degrees.

\lec{10-31}
Friedberg Splitting Theorem, Corollaries of the Sack's Splitting Theorem.
\prob (Trachtenbrock see p.121 2.5)
\par Define $A$ is autoreducible iff there exists $e$ such that
for all $x$,
$$\{e\}^{A\setminus\{x\}}(x)\downarrow=\psi_A(x)$$
Prove
\par (a) $\forall B\;\;\exists A\equiv_m B$ such that $A$ is autoreducible.
\par (b) there exist a ce $A$ which is not autoreducible.
\par (c) there exist a low ce $A$ which is not autoreducible.
\par (d)* there exist a ce $A\equiv_T K$ which is not autoreducible?

\lec{11-2}
Sacks Splitting Theorem.

\lec{11-5}
(Friedberg) Unique effective enumeration of all ce sets.
Dekker deficiency set is hypersimple.
\prob * Prove there is a partial computable $\psi$ such that
for every $e$ there is a unique $i$ such that $\varphi_e=\psi_i$.

\lec{11-7} Equivalent definitions of hypersimple:
\par  for
any computable sequence
$\exists^\infty k$ with $[n_k,n_{k+1})\subseteq A$,
\par if $\overline{A}=\{b_0<b_1<\cdots\}$ then for every computable
$f$ $\exists^\infty n \;f(n)<b_n$.
\par\medskip (Nerode)
$A\leq_{tt}B$ iff Turing reducible by machine which always converges
for any oracle iff Turing recucible by a computable time bounded oracle
machine.
\prob Prove or disprove:
\par (a) there exists $V$ ce such that $\{V_e:e\in \omega\}=$ set of simple sets.
\par (b) there exists $V$ ce such that $\{V_e:e\in \omega\}=$ set of ce nonsimple sets.
\par (c) there exists $V$ ce such that $\{V_e:e\in \omega\}=$ set of ce coinfinite sets.
\par (d) there exists $V$ ce such that $\{V_e:e\in \omega\}=$ set of cofinite sets.
\par \bigskip Extra credit: In case its true, show that there is a unique
enumeration as in Friedberg's Theorem.

\prob Prove that $\leq_{tt}$ is transitive.

\lec{11-9}
(Post) If $K\leq_{tt}A$, then $A$ not hypersimple. Example of a simple
$A$ with $K\leq_{tt}A$.  Equivalent definitions of hyperhypersimple.

\prob Prove that for every $A$ ce with $\overline{A}$ infinite there
exists a hypersimple $B\supseteq A$.

\lec{11-12}
Examples of hypersimple but not hyperhypersimple sets, Maximal set
is hyperhypersimple, (Friedberg) Maximal sets exist.

\lec{11-14}
There exists a  maximal set $M\equiv_TK$. Example of $h^2$-simple set
which is not maximal: $M_1\cap M_2$ where $M_i$ maximal and
$M_1\not=^* M_2$.

\prob Let $A$ be $h^2$-simple and $f:\omega\to A$ a computable 1-1
onto enumeration. Prove that $B=\{f(n):n\in A\}$ is $h^2$-simple
but not maximal.

\prob Let $A_0,A_1$ be a Friedberg splitting of a maximal set $M$, ie., $M$
is the disjoint union of the $A_i$ and each $A_i$ is ce but not computable.
Prove that $A_0$ is nowhere simple, ie. for any $R$ computable if
$R\cap\overline{A_0}$ is infinite, then it contains an infinite ce set.

\lec{11-16}
Turing degree of a maximal set is high, a ce degree is high iff
it contains a dominating function. Definable subsets of the
lattice of ce sets, ${\cal E}$, eg. computable, finite, simple, maximal.

\prob Suppose $A$ is $h^2$-simple and $\overline{A}=\{b_0<b_1<\cdots\}$.
let $f$ be a computable function.
Prove that $\forall^\infty n \; f(n)<b_n$.  See p.212 - 1.11

\lec{11-19}
(Lachlan) $A$ is $h^2$-simple iff for all ce $B\supseteq A$ there
exists ce $C\supseteq A$ with $B\cap C=A$ and $B\cup C=\omega$.
Example of nontrivial automorphism of ${\cal E}$, i.e. $\pi$ identity
on maximal set.

\prob (Martin p.198-5.5) Show there exists a nontrivial ce set
with no maximal superset.

\lec{11-21}
(Martin) There exists $\pi$ an automorphism of ${\cal E}$ and
a hypersimple set $A$ such that $\pi(A)$ is not hypersimple.

\prob Prove or disprove: Suppose $\pi:\omega\to\omega$ is a bijection
and $\pi^{-1}(C)\in {\cal E}$ for every $C\in {\cal E}$.  Then
$\pi(C)\in {\cal E}$ for every $C\in {\cal E}$, ie. $\pi$ gives an
automorphism of ${\cal E}$.
\par Hint: Use a maximal set.

\lec{11-26}
(Sacks) There exists a nontrivial high degree. (Shoenfield) Thickness Lemma.

\lec{11-28}
True stages, window lemma. Sacks Jump Theorem.

\lec{11-30} Finish proof of Jump Theorem. Non-trivial $L_n$ and
$H_n$ degrees, a ce set $A$ such that $0^{(n)}<_T A^{(n)}<_T 0^{(n+1)}$
for all $n$.

\lec{12-3}
Sacks Density Theorem.

\lec{12-5}
Sacks Density Theorem (continued).

\lec{12-7}
Final claim in proof of Sacks Density Theorem.  Stated
Robinson Jump Interpolation and derived some corollaries.

\prob (Robinson) Prove that for any ce sets $C,D$ with
$D<_T C$ there exists ce sets $A$ and $B$ such that
\par (a) $A$ and $B$ are $\leq_T$ incomparable, and
\par (b) $D<_T A <_T C$ and $D<_T B <_T C$.


\bigskip
The last three problems can be proved as Corollaries of (possibly relativized
versions of) Sack's Splitting, Robinson Jump Interpolation, and the
Recursion Theorem.

\bigskip
\prob Prove that if $A$ is ce and has low degree, then there exists ce
sets $B$ and $C$ such that
\par (a) $A\leq_T B$ and $A\leq_T C$,
\par (b) $B$ and $C$ are $\leq_T$ incomparable, and
\par (c) $B'$ and $C'$ are $\leq_T$ incomparable

\prob Prove that if $A$ is ce and not computable there exists ce sets
$B$ and $C$ such that
\par (a) $B\leq_T  A$ and $C\leq_T A$,
\par (b) $B$ and $C$ are $\leq_T$ incomparable, and
\par (c) $A'\equiv_T B'\equiv_T C'$.

\prob Prove there exists a ce sets $A$ and $B$ such that for every $n$
\par (a) $A^{(n)}<_T 0^{(n+1)}$ and $B^{(n)}<_T 0^{(n+1)}$ and
\par (b) $A^{(n)}\oplus B^{(n)} \equiv_T 0^{(n+1)}$

\lec{12-10}
Friedberg-Muchnik on a tree.  Lachlan-Yates minimal pair strategy for
a single negative requirement.

\lec{12-12}
Minimal pairs using trees.

\lec{12-14}
Minimal pair of high degrees.

\bigskip
Handout: Bootleg copy of Julia Knight, Chris Ash, Computable structures and
the hyperarithmetical hierarchy, Chapters 4-5. The remaining time was spent
proving
 $$\Delta^1_1=HYP$$
Some details were omitted.

The same material is covered in the first 30 pages of Gerald Sacks book,
Higher recursion theory.  And also somewhere in Hartley Rogers book.


\end{document}