\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{comment} 

\newcommand{\NP}{{\rm NP}}
\renewcommand{\P}{{\rm P}}
\newcommand{\IS}{{\rm ISAAC}}
\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{\goes}{\rightarrow}
\newcommand{\nth}{n^{th}}
\newcommand{\N}{\sf{N}}
\newcommand{\Q}{\sf{Q}}
\newcommand{\R}{\sf{R}}
\newcommand{\C}{\sf{C}}
\newcommand{\Z}{\sf{Z}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\es}{\emptyset}
\newcommand{\st}{\mathrel{:}}
\newcommand{\e}{\varepsilon}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}


\begin{document}


\centerline{\bf Homework 10 Morally Due April 30 at 3:30PM}

\begin{enumerate}
\item 
(30 points)

\begin{enumerate}
\item
(30 points) 
Let $f$ be a computable function from $\N$ to $\N$ such that 

$$(\forall x,y)[x<y \goes f(x)<f(y)].$$

(so $f$ is increasing). 

Show that the set of numbers in the image of $f$ is decidable. 
Formally the image is

$$\{ y \st (\exists x)[f(x)=y]\}.$$

\item 
(0 points but I want you to think about this one)

Let $f$ be a computable function from $\N$ to $\N$ such that 

$$(\forall x,y)[x<y \goes f(x)\le f(y)].$$

(so $f$ is monotonically increasing). 

IS the image of $f$ decidable? THINK ABOUT IT. 

\end{enumerate} 

\newpage 

\item
(30 points) Show that the following problem is DECIDABLE:

Given a polynomial $p(x) = a_nx^n + \cdots + a_0$ where $a_n,\ldots,a_0\in\Z$.
determine if  $p$ have a root in $\Z$. 

({\bf Hint} Your first step is to rewrite $p(x)$ as 

$p(x) = x(a_nx^{n-1} + \cdots + a_1) + a_0$.

Your next step is to set this to 0 and see if that bounds what $x$ can be. 


\newpage


\item 
(40 points)
\begin{enumerate}
\item
(10 points) 
Using the WS1S convention give a DFA for

$$\{ (x,y) \st x=y+1 \}.$$

How many states does your DFA have? 

(All states are labelled A for accept or R  for reject or S for stupid.) 

\item
(10 points) 
Using the WS1S convention give a DFA for

$$\{ (x,y) \st x=y+2 \}.$$

How many states does your DFA have? 

(All states are labelled A for accept or R  for reject or S for stupid.) 

\item
(20 points) 
Let $a\in\N$ and $a\ge 1$. 
Using the WS1S convention give a DFA for

$$\{ (x,y) \st x=y+a \}.$$

You will need to use DOT DOT DOT.

How many states does your DFA have have as a function of $a$? 

(All states are labelled A for accept or R  for reject or S for stupid.) 
\end{enumerate}


\end{enumerate}

\end{document}