\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 10 CMSC 452. Morally Due May 7}

\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
(60 points --- 15 points for each part)
\begin{enumerate}
\item
Let $M$ be a Turing machine.
Show that the following set is $\Sigma_1$:

$$\{ x \mid M(x)\cvg \}$$

\item
Describe an algorithm $M$ such that 

$$\{ x \mid M(x)\cvg \}$$

is undecidable.

(HINT- Write an $M$ such that the set 
$$\{ x \mid M(x)\cvg \}$$ 
is HALT.
Recall that HALT is

$$\{ e \mid M_e(e)\cvg \}$$

)

\item
Let $M$ be a Turing machine.
Show that the following set is $\Sigma_1$:

$$\{ y \mid \hbox{ there is some $x$ such that $M(x)=y$ } \}$$

\item
Describe an algorithm $M$ such that 

$$\{ y \mid \hbox{ there is some $x$ such that $M(x)=y$ } \}$$

is undecidable.

(HINT- Write an $M$ such that the set
$$\{ y \mid \hbox{ there is some $x$ such that $M(x)=y$ } \}$$
is HALT.

)


\end{enumerate}

\newpage

\item
(40 points --- 20 points each)
A NATHAN program is a program that can, on each input, make 10 queries to HALT.

\begin{enumerate}

\item
Is there a NATHAN program for the following problem: on input $(e_1,\ldots,e_{100})$
determine EXACTLY which $e_i$ are such that $M_{e_i}(0)\cvg$?
(Formally the output is a bit string $(b_1,\ldots,b_{100})$ such that,
for all $1\le i\le 100$, 

$$M_{e_i}(0)\cvg\hbox{ iff }b_i=0.$$
)

\item
Is there a NATHAN program for the following problem: on input $n$ viewed as a number written
in binary, output some string $y$ such that 
$C(y)\ge n$ ($C(y)$ is the Kolmogorov complexity of $y$ --- the size of the smallest Turing Machine
that prints out $y$ on input 0.)
\end{enumerate}


\end{enumerate}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: