% LaTex2e \documentclass[12pt]{article} \usepackage{amssymb,latexsym} \def\res{{\upharpoonright}} \def\qed{{$\Box$}} \def\proof{{\par\noindent Proof\par}} \def\dex#1{{\it #1}} \newcommand{\dotminus}{\dot{-}} \newcommand{\blank}{\;\tilde{ }\;} \newcount\probno \probno=0 \def\prob{\advance\probno by 1 \par\bigskip\noindent\the\probno . } \begin{document} \begin{flushleft} M773 Computability Theory Fall 2001\\ A.Miller\\ 403 Van Vleck \\ officer hours: M W 3:30-5:00\\ miller@math.wisc.edu \\ www.math.wisc.edu/$\sim$miller/m773/index.html \\ Prerequisite: None\\ Textbook: Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag (1987) out of print\\ Grading: One homework exercise assigned daily and due one week latter in class.\\ \end{flushleft} Recursively enumerable sets are those which can be listed by an effective procedure. Two sets have the same (Turing) degree if there are effective procedures reducing each to the other. Topics: Unsolvable problems - a universal Turing machine Kleene's recursion theorem - Blum's speed up theorem The arithmetic hierarchy, classifying definable sets Post's simple sets, hypersimple sets, and hyperhypersimple sets Spector's minimal Turing degree Friedberg-Muchnik Theorem and finite injury priority arguments Friedberg's maximal set construction, enumeration without repetition Lachlan-Yates Minimal pairs, Sacks density - infinite injury priority Recursive ordinals, hyperarithmetic hierarchy, and Kleene's O. \bigskip A few years ago Soare decided that the terminology ``recursive function, recursive set, recursively enumerable set, recursion theory'' should be changed to ``computable function, computable set, computably enumerable set, computability theory'' etc. I think most everyone in this field now uses the new terminology. Maybe this is why his book is out of print. We have received permission by Springer-Verlag to copy his book for a small fee. \bigskip The following pages are taken from my book: http://www.math.wisc.edu/$\sim$miller/res/index.html see Introduction to Mathematical Logic - Moore style logintro.abs ... logintro.tex ... logintro.ps ... \newpage \begin{center} {\bf Turing Machines and Computable Functions} \end{center} A \dex{Turing machine} is a function $m$ such that for some finite sets $A$ and $S$ the domain of $m$ is a subset of $S \times A$ and range of $m$ is a subset of $S \times A \times \{l,r\}$. We call $A$ the alphabet and $S$ the states. For example, suppose $S$ is the set of letters $\{a,b,c,\ldots,z\}$ and $A$ is the set of all integers less than seventeen, then $m(a,4)=(b,6,l)$ would mean that when the machine $m$ is in state $a$ reading the symbol $4$ it will go into state $b$, erase the symbol $4$ and write the symbol $6$ on the tape square where $4$ was, and then move left one square. \bigskip \noindent \input turing3.pic \input turing4.pic \bigskip If $(a,4)$ is not in the domain of $m$, then the machine halts. This is the only way of stopping a calculation. Let $A^{<\omega}$ be the set of all finite strings from the alphabet A. The Turing machine $m$ gives rise to a partial function $M$ from $A^{<\omega}$ to $A^{<\omega}$ as follows. We suppose that $A$ always contains the blank space symbol $\blank$; and $S$ contains the starting state $a$. Given any word $w$ from $A^{<\omega}$ we imagine a tape with $w$ written on it and blank symbols everywhere else. We start the machine in state $a$ and reading the leftmost symbol of $w$. A configuration consists of what is written on the tape, which square of tape is being read, and the state the machine is in. Successive configurations are obtained according to rules determined by $m$, namely if the machine is in state $q$ reading symbol $s$ and $m(q,s)=(q^\prime,s^\prime,d)$ then the next configuration has the same tape except the square we were reading now has the symbol $s^\prime$ on it, the new state is $q^\prime$, and the square being read is one to the left if $d=l$ and one to the right if $d=r$. If $(q,s)$ is not in the domain of $m$, then the computation halts and $M(w)=v$ where $v$ is what is written on the tape when the machine halts. Suppose $B$ is a finite alphabet that does not contain the blank space symbol $\blank $ then a function $f:B^{<\omega}\to B^{<\omega}$ is a \dex{partial recursive function} iff there is a Turing machine $m$ with an alphabet $A\supseteq B$ such that $f = M\res B^{<\omega}$. A partial recursive function is \dex{recursive} iff it is total. A function $f:\omega \to \omega$ is recursive if it is recursive when considered as a map from $B^{<\omega}$ to $B^{<\omega}$ where $B=\{1\}$. Words in $B$ can be regarded as numbers written in base one, hence we identify the number $x$ with $x$ ones written on the tape. For example, the identity function is recursive, since it is computed by the empty machine. The successor function is recursive since it is computed by the machine: \input turing1.pic In the diagram on the left, states are represented by little circles. The arrows represent the \dex{state transition function} $m$. For example, the horizontal arrow represents the fact that when $m$ is in state $a$ and reads $\blank$ then it writes $1$, moves right, and goes into state $b$. The set of strings of zeros and ones with an even number of ones is recursive. Its characteristic function (parity checker) can be computed by the following machine: \input turing2.pic The following problems are concerned with recursive functions and predicates on $\omega$. \bigskip \prob Show that any constant function is recursive. \prob A binary function $f:\omega\times\omega\to\omega$ is recursive iff there is a machine such that for any $x,y\in\omega$ inputing $x$ ones and $y$ ones separated by ``,'' the machine eventually halts with $f(x,y)$ ones on the tape. Show that $f(x,y) = x+y$ is recursive. \prob Show that $g(x,y) = x y$ is recursive. \prob Let $ x \dotminus y = max\{ 0,x-y \}.$ Show that $p(x)= x \dotminus 1$ is recursive. Show that $ q(x,y)= x\dotminus y $ is recursive. \prob Suppose $f(x)$ and $g(x)$ are recursive. Show that $f(g(x))$ is recursive. \prob Formalize a notion of multitape Turing machine. Show that we get the same set of recursive functions. \prob Show that we get the same set of recursive functions even if we restrict our notion of computation to allow only tapes that are infinite in one direction. \prob Show that the family of recursive functions is closed under arbitrary compositions, for example $f(g(x,y),h(x,z),z)$. More generally, if $f(y_1,\ldots,y_m)$, $g_1(x_1,\ldots,x_n),\ldots$, and $g_m(x_1,\ldots,x_n)$ are all recursive, then so is $$f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n)).$$ \prob A set is recursive iff its characteristic function is. Show that the binary relation $x=y$ is recursive. Show that the binary relation $ x\leq y $ is recursive. \prob Define $$ sgn(n) = \left\{ \begin{array}{ll} 0 & \mbox{ if } n=0 \\ 1 & \mbox{ otherwise} \end{array} \right.$$ Show it is recursive. \prob Show that if $A \subseteq \omega$ is recursive then so is $ \omega \setminus A.$ Show that if $A$ and $B$ are recursive so is $ A \cap B$ and $ A \cup B$. \prob Suppose g(x) and h(x) are recursive and A is a recursive set. Show that f is recursive where: $$ f(x) = \left\{ \begin{array}{ll} g(x) & \mbox{ if } x \in A \\ h(x) & \mbox{ if } x \notin A \end{array} \right.$$ \prob Show that the set of even numbers is recursive. Show that the set of primes is recursive. \prob Show that $e(x,y)=x^y$ is recursive. Show that $f(x)=x!$ is recursive. \prob Suppose that $h(z)$ and $g(x,y,z)$ are recursive. Define $f$ by recursion, $f(0,z)=h(z)$ and $f(n+1,z) = g( n,z, f(n,z) )$. Show that $f$ is recursive. \prob We say that a set $ A \subseteq \omega$ is \dex{recursively enumerable} (re) iff it is the range of a total recursive function or the empty set. Show that a set is re iff it is the domain of a partial recursive function. \prob Show that every recursive set is re Show that a set is recursive iff it and its compliment are re. \prob Show that if $f$ is an increasing total recursive function then the range of $f$ is recursive. \prob Suppose that $f:\omega\to\omega$ and $g:\omega\to\omega$ are recursive functions such that $f(m)