\documentclass[12pt]{article}

\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\N}{{\sf N}}
\newcommand{\goes}{\rightarrow}
\newcommand{\st}{\mathrel{:}}
\newcommand{\nth}{n^{th}}
\newcommand{\HALTONZ}{{\rm HALTON0 }}
\newcommand{\HALTONZns}{{\rm HALTON0}}

\newcommand{\es}{\emptyset}

\begin{document}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf Homework 9 Morally DUE May 4 at 11:00 AM}

\centerline{\bf THIS HW IS TWO PAGES LONG!!!!!!!!!!!!!!!!!!}

\begin{enumerate} %ENUM

\item
(35 points)
Give the reduction $3COL \le SAT$.


\item
(35 points)
We assume all Turing Machines have $\Sigma=\{1,2,3\}$ and 3 is the \# symbol.
and the state set $Q$ is an initial
segment of $\N-\{0\}$ (that is, it will be something like $\{1,2,3,4\}$).

\begin{enumerate}
\item
Describe a procedure to code Turing Machines into $\N$ such that the following holds:
\begin{itemize} %ENUM
\item
Two different Turing Machines map to different numbers.
(Though it is okay if some numbers do not get mapped to.)
\item
The following should be computable:

Input: $x,y\in\N$

Output: 

If $x$ does not code a number than output THATSBSMAN.

If $x$ does code a number than let it be $M_x$. Run $M_x(y)$
(this might diverge, and that's fine.)

\end{itemize} %ENUM
HINT- do not over think this. Any way you code a TM into numbers should work.
\item
Let $M$ be the TM: $Q=\{1,2,3\}$, $\Sigma=\{1,2,3\}$, $s=1$, $h=3$,

$\delta(1,1)=(1,L)$. 

$\delta(1,2)=(1,2)$.

$\delta(1,3)=(2,R)$. 

$\delta(2,1)=(4,1)$. 

$\delta(2,2)=(3,3)$. 

$\delta(2,3)=(3,L)$. 

Use your procedure to encode this into a number. Show your work and give us your number.
(If your number involves the product of numbers, you need not multiply them together.
For example, if the above codes to $2^{7^6}\times 3^{4^5}$ then you can leave it in that form
and not do the multiplication.)

\end{enumerate}

\centerline{\bf GOTO THE NEXT PAGE}

\newpage

\item
(30 points)
During this problem we will use $M_1,\ldots,M_{100}$ to mean
ANY 100 Turing Machines. They are not associated to any numbering.

HALTON0 is the set of all Turing Machines that halt on input 0.

\begin{enumerate} %ENUM
\item
(10 points)
Bill gives you 100 Turing Machines $M_1,\ldots,M_{100}$.
He wants to know if {\it at least 17 of them are in HALTON0}.

Come up with a Turing Machine $M$ (by that I mean just write psuedocode
that uses $M_1,\ldots,M_{100}$) so that

$$M\in \HALTONZ\hbox{ iff at least 17 of $M_1,\ldots,M_{100}$ are in HALTON0}.$$

\item
(10 points)
Bill gives you 100 Turing Machines $M_1,\ldots,M_{100}$.
He wants to know HOW MANY are in HALTON0.

If you could ASK HALTON0 100 questions then you could do this---just ask
$M_1\in \HALTONZ?$,
$M_2\in \HALTONZ?$,$\ldots$,
$M_{100}\in \HALTONZ?$ and output the number that returned YES.

\medskip

What if you can ask HALTON0 less than 100 questions? Find a number $q<100$
such that you can determine HOW MANY are in HALTON0  with $q$ questions to HALTON0.
Write psuedocode (which will make $q$ queries to $\HALTONZ$) that 
will, on input $M_1,\ldots,M_{100}$, output HOW MANY of them are in $\HALTONZ$
(so the output is a number between 0 and 100).
Try to make $q$ as small as you can.
(HINT: Use part (a).)


\item
(10 points)
Bill gives you 100 Turing Machines $M_1,\ldots,M_{100}$.
He wants to know WHICH ONES halt on 0.

If you could ASK HALTON0 100 questions then you could do this---just ask
$M_1\in \HALTONZ?$,
$M_2\in \HALTONZ?$,$\ldots$,
$M_{100}\in \HALTONZ?$ and see see which ones return YES.

\medskip

What if you are allowed to ask HALTON0 less than 100 questions? IS there a number $q<100$
such that you can determine WHICH of $M_1,\ldots,M_{100}$ are in HALTON0 with
$q$ questions to HALTON0? Prove your result.
\end{enumerate} %ENUM

\end{enumerate} %ENUM

\end{document} %ENUM