\documentclass[12pt,ifthen]{article} \usepackage{url} \usepackage{comment} \usepackage{amsmath, amssymb, amsthm, amstext, mathtools, graphicx, url} \usepackage{hyperref} \newif{\ifshowsoln} \showsolntrue \begin{document} \DeclarePairedDelimiter{\ceil}{\lceil}{\rceil} \newcommand{\CLIQ}{{\rm CLIQ}} \newcommand{\FINDCLIQ}{{\rm FINDCLIQ}} \newcommand{\SCLIQ}{{\rm SCLIQ}} \newcommand{\bits}[1]{{\{0,1\}^{#1}}} \newcommand{\Z}{{\sf Z}} \newcommand{\N}{{\sf N}} \newcommand{\Q}{{\sf Q}} \newcommand{\R}{{\sf R}} \newcommand{\C}{{\sf C}} \newcommand{\into}{\rightarrow} \newcommand{\cvg}{\downarrow} %\newcommand{\implies}{\rightarrow} \newcommand{\st}{\mathrel{:}} \centerline{\bf HW 9 CMSC 452. Morally Due April 30} \centerline{\bf THIS HW IS TWO PAGES LONG!!!!!!!!!} {\bf Throughout this HW $M_1,M_2,\ldots$ is a standard list of Turing Machines. Can also view as a list of all partial computable functions.} \begin{enumerate} \item (30 points) Answer TRUE OR FALSE and prove it. Assume input and output take values in \(\N\). \begin{enumerate} \item (15 points) Let $f$ be a computable function such that for all $xf(y)$. Then the IMAGE of $f$ is computable. \item (0 points --- but think about) Let $f$ be a computable function such that for all $x p_{j}(x)$ on all but a finite number of inputs), then there is SOME $x$ such that $p_{i}(y) > p_{j}(y)$ for all $y>x$.) And NOW finally the question: \begin{enumerate} \item (15 points) Show that there exists a COMPUTABLE function $g$ that DOMINATES all $YAELLE$ functions. \item (15 points) Show that if a function $f$ DOMINATES all YAELLE functions, then $f$ is NOT a $YAELLE$ function. \end{enumerate} \item (40 points) Let $p_1,p_2,\ldots$ be all the primitive recursive functions. For each of the following sets WRITE IT using quantifiers and try to get it as low as possible in the arithmetic hierarchy (i.e., given set $X$ try to find the least $n \in \N$ such that $X \in \Sigma_n$ or $X \in \Pi_n$). STATE for each one where it is (e.g., $X \in \Sigma_{100}$). \begin{enumerate} \item (10 points) $$A=\{ (i,j) \mid p_i \hbox{ and } p_j \hbox{ are the same function } \}$$ \item (10 points) $$B=\{ (i,j) \mid p_i \hbox{ dominates } p_j \}$$ \item (10 points) $$C=\{ i \mid M_i \hbox{ halts on all but at most 2 inputs } \}$$ \item (10 points) $$D=\{ i \mid M_i \hbox{ halts on all but a finite number of inputs } \}$$ \end{enumerate} \end{enumerate} \end{document}