% This work is licensed under the Creative Commons Attribution 3.0 Unported License.
% To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/
% or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, 
% California, 94105, USA.
%
% Author: Alejandro Diaz-Caro <alejandro.diaz-caro@imag.fr>
% Date: November 2010
\documentclass[12pt,a4paper]{article}

\usepackage{amsmath,amsfonts,amssymb}
\usepackage[top=1.5cm,right=1.5cm,bottom=1.5cm,left=1.5cm]{geometry}
\usepackage{vaucanson-g}
\usepackage{mathdots}
\newcommand{\sol}{\noindent\underline{\textsc{Solution}}~}
\newcommand{\N}{\ensuremath{\mathbb{N}_0}}
\newcommand{\ie}{{\em i.e.}~}
\newcommand{\cf}{{\em cf.}~}
\newcommand{\Oh}{\ensuremath{\mathcal{O}}}
\newcommand{\eg}{{\em e.g.}~}
\newcommand{\RFF}{{\bf PRF}}
\newcommand{\RFS}{{\bf PRS}}
\newcommand{\RFR}{{\bf PRR}}
\newcommand{\RF}{{\bf RF}}
\newcommand{\D}{\ensuremath{{}^\circ\! D}}
\newcommand{\di}{\ensuremath{{}^\circ\! d}}

\makeindex

\title{Exercise sheet 6: Review}
\author{Alejandro D\'iaz-Caro}
\date{2010}

\begin{document}
\begin{center}
 \textbf{\begin{large}Exercise sheet 6: Review\end{large}} -- \textsc{Corrections}
\end{center}

\begin{enumerate}
\subsection*{Turing machines}
 \item Consider a $k$-head Turing machine having a single tape and $k$ heads; more than one head can be on the same cell at a time. At each move, the TM will read the symbols under its heads, and consider its internal state (a unique state for whole machine), then it changes the state, writes a symbol on each cell under a head (if there are more than one head in the same cell, it writes the symbol with only one of them) and moves each head to the left or to the right independently. Prove that the languages accepted by $k$-head Turing machines are the same languages accepted by ordinary TM's.
\medskip

\sol   We must prove that the $k$ head TM can be simulated by an ordinary TM. Since we already know that a multiple-tape TM can be simulated with an ordinary one, it suffices to simulate the $k$-head TM with a multiple-tape TM. We call $K$ to the $k$-tape TM and $M$ to the multiple-tape TM that simulates the former.

Assume we enumerate each head as $h_i$ with $i=1,\dots,k$. We use a $k+1$-tape TM $M$ to do the simulation. The first step is to copy the input tape of $K$ into each tape of $M$. In the last tape, we call it `extra', we add a mark to each symbol where there is a head in $K$ (add a mark means that the alphabet of machine $M$ is the union of the alphabet of the machine $K$ plus the set of all the symbols in the alphabet, with a mark).

So, we get the following picture:

Let the machine $K$ be in the following configuration:

	\hfill\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c}
		\multicolumn{1}{c}{}&\multicolumn{1}{c}{$\downarrow_1$} & \multicolumn{1}{c}{}  &\multicolumn{1}{c}{\!\!$\downarrow_{23}$} & \multicolumn{3}{l}{} &\multicolumn{1}{c}{$\downarrow_4$} & \multicolumn{5}{l}{}\\
		\hline 
		~& \makebox[9pt]{$\sigma$} & \makebox[9pt]{$\alpha$} & \makebox[9pt]{$\beta$} & \makebox[9pt]{$\delta$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\alpha$}&~\\
		\hline
	\end{tabular}

Then the machine $M$ is in the following configuration:

	\hfill\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c}
		\multicolumn{1}{c}{}&\multicolumn{1}{c}{$\downarrow$} & \multicolumn{1}{c}{}  &\multicolumn{1}{c}{} & \multicolumn{3}{l}{} &\multicolumn{1}{c}{} & \multicolumn{5}{l}{}\\
		\hline 
		~& \makebox[9pt]{$\sigma$} & \makebox[9pt]{$\alpha$} & \makebox[9pt]{$\beta$} & \makebox[9pt]{$\delta$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\alpha$}&~\\
		\hline 
		\multicolumn{1}{c}{}&\multicolumn{1}{c}{} & \multicolumn{1}{c}{}  &\multicolumn{1}{c}{$\downarrow$} & \multicolumn{3}{l}{} &\multicolumn{1}{c}{} & \multicolumn{5}{l}{}\\
		\hline
		~& \makebox[9pt]{$\sigma$} & \makebox[9pt]{$\alpha$} & \makebox[9pt]{$\beta$} & \makebox[9pt]{$\delta$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\alpha$}&~\\
		\hline
		\multicolumn{1}{c}{}&\multicolumn{1}{c}{} & \multicolumn{1}{c}{}  &\multicolumn{1}{c}{$\downarrow$} & \multicolumn{3}{l}{} &\multicolumn{1}{c}{} & \multicolumn{5}{l}{}\\
		\hline
		~& \makebox[9pt]{$\sigma$} & \makebox[9pt]{$\alpha$} & \makebox[9pt]{$\beta$} & \makebox[9pt]{$\delta$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\alpha$}&~\\
		\hline
		\multicolumn{1}{c}{}&\multicolumn{1}{c}{} & \multicolumn{1}{c}{}  &\multicolumn{1}{c}{} & \multicolumn{3}{l}{} &\multicolumn{1}{c}{$\downarrow$} & \multicolumn{5}{l}{}\\
		\hline
		~& \makebox[9pt]{$\sigma$} & \makebox[9pt]{$\alpha$} & \makebox[9pt]{$\beta$} & \makebox[9pt]{$\delta$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\alpha$}&~\\
		\hline
		\multicolumn{1}{c}{$\downarrow$}&\multicolumn{1}{c}{} & \multicolumn{1}{c}{}  &\multicolumn{1}{c}{}&\multicolumn{1}{c}{} &
\multicolumn{3}{l}{} &\multicolumn{1}{c}{} & \multicolumn{4}{l}{}\\
		\hline
		~& \makebox[9pt]{$\hat\sigma$} & \makebox[9pt]{$\alpha$} & \makebox[9pt]{$\hat\beta$} & \makebox[9pt]{$\delta$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\hat\beta$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\alpha$}&~\\
		\hline
	\end{tabular}

At each move in machine $K$, we do the same movement in the corresponding tape. Then, we check the last (extra) tape to see what are the changes with respect to each tape. We synchronize those changes one by one in the extra tape. For example, if in the tape $2$th the $3$th cell has been changed from $\beta$ to $\sigma$ and the head moves to the right, then after synchronizing such tape, the extra tape will looks as follows

	\hfill\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c}
	       		\hline
		~& \makebox[9pt]{$\hat\sigma$} & \makebox[9pt]{$\alpha$} & \makebox[9pt]{$\sigma$} & \makebox[9pt]{$\hat\delta$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\hat\beta$}& \makebox[9pt]{$\beta$}& \makebox[9pt]{$\sigma$}& \makebox[9pt]{$\alpha$}& \makebox[9pt]{$\alpha$}&~\\
		\hline
	      \end{tabular}

Then when we have to synchronize the $3$th tape we compare all the cells except those already synchronized (all except the $3$th cell in our example), so the extra tape remain unchanged.

After having synchronized all the tapes. We replicate the extra tape in all the other tapes, which finish the synchronization process and the movement.
\pagebreak

 \item Consider the numeric functions $f:\N^k\to\N$. 
 \begin{itemize}
	\item Natural numbers can be represented in unary form: {\em e.g.} $\bar{0}=1$, $\bar{1}=11$, $\bar{2}=111$, $\dots$. Hence we can take the input alphabet of a TM computing numeric functions to be $\Sigma=\{1\}$.
	\item Consecutive numbers on the input are separated by a blank space $\square$.
	\item The TM starts its computation with the head placed on the $\square$ preceding the first number. 

	\eg for $f(2,0,3)$:
	\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c}
		\multicolumn{13}{l}{$q_0$}\\
		\multicolumn{1}{c}{}&\multicolumn{1}{c}{$\downarrow$} & \multicolumn{11}{l}{}\\
		\hline ~& \makebox[9pt]{} & \makebox[9pt]{$1$} & \makebox[9pt]{$1$} & \makebox[9pt]{$1$}& \makebox[9pt]{}& \makebox[9pt]{$1$}& \makebox[9pt]{}& \makebox[9pt]{$1$}& \makebox[9pt]{$1$}& \makebox[9pt]{$1$}& \makebox[9pt]{$1$}&~\\
		\hline
	\end{tabular}
	\item When the computation terminates, then input has been replaced on the tape with the result of the function.

	\eg if $f(2,0,3)=4$:
	\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c}
		\multicolumn{13}{l}{$q_f$}\\
		\multicolumn{1}{c}{}&\multicolumn{1}{c}{$\downarrow$} & \multicolumn{11}{l}{}\\
		\hline ~& \makebox[9pt]{} & \makebox[9pt]{$1$} & \makebox[9pt]{$1$} & \makebox[9pt]{$1$}& \makebox[9pt]{$1$}& \makebox[9pt]{$1$}& \makebox[9pt]{}& \makebox[9pt]{}& \makebox[9pt]{}& \makebox[9pt]{}& \makebox[9pt]{}&~\\
		\hline
	\end{tabular}
\end{itemize}
 We make some assumptions to ease composition of TM's:
	\begin{itemize}
	 \item There is a single final state $q_f$. The TM halts with the head over the $\square$ just before the solution.
	 \item The only transition from $q_0$ is $\delta(q_0,\square)=(q_i,\square,R)$	.
	 \item There are no transitions entering $q_0$ or of the form $\delta(q_f,\square)$.
	 \item The computation loops whenever $f(m)$ is undefined.
	\end{itemize}
 This allows us to sequentially compose TM's, as represented by the following diagram
	\begin{center}
	\begin{tabular}{c@{}c@{}c@{}c@{}c}
	$\stackrel{(\textrm{I})}{\longrightarrow}$ & \fbox{$M_1$} & $\stackrel{(\textrm{II})}{\longrightarrow}$ & \fbox{$M_2$} & $\stackrel{(\textrm{III})}{\longrightarrow}$
	\end{tabular}
	\end{center}
	\begin{description}
	 \item[I] Initial state of $M_1$ and of the combination. 
	 \item[II] Final state of $M_1$ and initial state of $M_2$.
	 \item[III] Final state of $M_2$ and also of the combination.
	\end{description}
	\begin{enumerate}
	 \item Construct a TM computing the successor function $s(n)=n+1$.

\sol   
	$$\begin{array}{r@{\ =\ }l}
	\delta(q_0,\square) & (q_1,\square,R)\\
	\delta(q_1,1) & (q_1,1,L)\\
	\delta(q_1,\square) & (q_f,1,L)
    \end{array}$$
\medskip

	 \item Construct a TM computing the zero function $z(X^k)=0$.

\sol 
	$$\begin{array}{r@{\ =\ }l}
	\delta(q_0,\square) &  (q_1,\square,R)\\
	\delta(q_1,1)  &  (q_1,\square,R)\\
	\delta(q_1,\square)  & (q_2,\square,R)\\
	\delta(q_2,1) & (q_1,\square,R)\\
	\delta(q_2,\square) & (q_f,1,L)
	\end{array}$$
\medskip

	 \item Construct a TM computing the empty function, \ie the function that is undefined for every $n\in\N$.

\sol 
	$$\begin{array}{r@{\ =\ }l}
	\delta(q_0,\square) &  (q_1,\square,R)\\
	\delta(q_1,1)  &  (q_1,1,R)\\
	\delta(q_1,\square)  & (q_1,\square,R)
	\end{array}$$
\medskip

	 \item Construct a TM computing the projector $u_k^{(n)}(x_1,\dots,x_k,\dots,x_n)=x_k$.

\sol 
	$$\begin{array}{r@{\ =\ }l}
	\delta(q_0,\square) &  (q_1,\square,R)\\
	\delta(q_i,1)  &  (q_i,\square,R)\hspace{0.5cm}\textrm{with }i=1,\dots,k-1\\
	\delta(q_i,\square) & (q_{i+1},\square,R)\hspace{0.5cm}\textrm{with }i=1,\dots,k-1\\
	\delta(q_k,1) & (q_k,1,R)\\
	\delta(q_k,\square) & (q_m,\square,R)\\
	\delta(q_m,1) & \delta(q_m,\square,R)\\
	\delta(q_m,\square) & (q_n,\square,R)\\
	\delta(q_n,1) & (q_m,\square,R)\\
	\delta(q_n,\square) & (q_v,\square,L)\\
	\delta(q_v,\square) & (q_v,\square,L)\\
	\delta(q_v,1) & (q_w,1,L)\\
	\delta(q_w,1) & (q_w,1,L)\\
	\delta(q_w,\square) & (q_l,\square,L)\\
	\delta(q_l,\square) & (q_f,\square,R)
	\end{array}$$
\medskip

	 \item Construct a TM computing the predecesor function $Pd(n)=\left\{\begin{array}{ll}0&\textrm{ if }n=0\\ n-1 & \textrm{otherwise}\end{array}\right.$

\sol 
	$$\begin{array}{r@{\ =\ }l}
	\delta(q_0,\square) &  (q_1,\square,R)\\
	\delta(q_1,1)  &  (q_2,\square,R)\\
	\delta(q_2,\square)  & (q_f,1,R)\\
	\delta(q_2,1)  & (q_f,1,L)\\
	\end{array}$$
\medskip

	 \item Using sequential composition, construct a TM computing the constant function $one$.\\
	Tip: $one=\Phi(s^{(1)},z^{(n)})$.

\sol 
	$$z^{(n)}\left\lbrace\begin{array}{r@{\ =\ }l}
	\delta(q_0,\square) &  (q_1,\square,R)\\
	\delta(q_1,1)  &  (q_1,\square,R)\\
	\delta(q_1,\square)  & (q_2,\square,R)\\
	\delta(q_2,1) & (q_1,\square,R)\\
	\delta(q_2,\square) & (q_{\mathbf{3}},1,L)
	\end{array}\right.$$
	$$s^{(1)}\left\lbrace\begin{array}{r@{\ =\ }l}
	\delta(q_{\mathbf{3}},\square) & (q_{\mathbf{4}},\square,R)\\
	\delta(q_{\mathbf{4}},1) & (q_{\mathbf{4}},1,L)\\
	\delta(q_{\mathbf{4}},\square) & (q_f,1,L)
    \end{array}\right.$$
	\end{enumerate}
\medskip

\subsection*{Recursive functions}
 \item Let $\lessdot$ be a primitive recursive relation. Show that the following functions are recursive.
	\begin{enumerate}
	 \item $f_1(x,y_0,y)=$ the first value $z$ in $[y_0,y]$ for which $x\lessdot z$.

\sol  Notice that 
$$f_1(x,y_0,y)=\mu_z(\D(\chi_{\geq}(z,y_0).\chi_{\geq}(y,z).\chi_{\lessdot}(x,z))=0)$$
so let $g(z,x,y_0,y)$ be the following function
$$\Phi(\D,\Phi(\Pi,\Phi(\Pi,\Phi(\chi_{\geq},u_1^{(4)},u_3^{(4)}),\Phi(\chi_{\geq},u_4^{(4)},u_1^{(4)})),\Phi(\chi_{\lessdot},u_2^{(4)},u_1^{(4)})))(z,x,y_0,y)$$
Then $f_1=M[g]$.
\medskip

	 \item $f_2(x,y)=$ the second value $z$ in $[0,y]$ for which $x\lessdot z$.

\sol  Notice that
$$f_2(x,y) = f_1(x,f_1(x,0,y)+1,y)$$
So $f_2=\Phi(f_1,u_1^{(2)},\Phi(f_1,u_1^{(2)},z^{(2)},u_2^{(2)}),u_2^{(2)})$.
	\end{enumerate}
\medskip

 \item Let $f$ and $g$ be primitive recursive functions. Show that the following function is also primitive recursive:
	$$h(x)=\left\{\begin{array}{ll}
	              1 & \textrm{ if }f(i)>g(j), \textrm{ for all }0\leq i\leq x\textrm{ and }0\leq j\leq x\\
				  0 & \textrm{ otherwise}
	              \end{array}\right.$$

\sol  We define $h$ using recursion.
$$\begin{array}{rcl}
h(0)	&=&	\left\lbrace\begin{array}{ll}
					1 & \textrm{ if }f(i)>g(j), \textrm{ for all }0\leq i\leq 0\textrm{ and }0\leq j\leq 0\\
					0 & \textrm{ otherwise}
					\end{array}\right.\\
					&	&	\\
		&=&	\left\lbrace\begin{array}{ll}
					1 & \textrm{ if }f(0)>g(0)\\
					0 & \textrm{ otherwise}
					\end{array}\right. \\
					&	&	\\
		&=&	\chi_>(f(0),g(0))\ =\ \Phi(\chi_>,\Phi(f,z^{(0)}),\Phi(g,z^{(0)}))\\
					&	&	\\
h(x+1) &=& h(x).\chi_>(f(x+1),g(x+1))\\
					&	&	\\
			&=& \Phi(\Pi,u_2^{(2)},\Phi(\chi_>,\Phi(f,\Phi(s,u_1^{(2)})),\Phi(g,\Phi(s,u_1^{(2)}))))(x,h(x))
\end{array}$$
So $h=R(\Phi(\chi_>,\Phi(f,z^{(0)}),\Phi(g,z^{(0)})),\Phi(\Pi,u_2^{(2)},\Phi(\chi_>,\Phi(f,\Phi(s,u_1^{(2)})),\Phi(g,\Phi(s,u_1^{(2)})))))$.
	\medskip

 \item Give primitive recursive definitions for the following functions
	\begin{enumerate}
	 \item half$(x)=\lfloor\dfrac{x}{2}\rfloor$.

\sol  We define half using recursion.
		$$\begin{array}{rcl}
			\textrm{half}(0) &=&0=z^{(0)}\\
			\textrm{half}(x+1) &=&\textrm{half}(x)+\chi_{odd}(x)\\
			&=&\Phi(\Sigma,u_2^{(2)},\Phi(\chi_{odd},u_1^{(2)}))(x,\textrm{half}(x))
		     \end{array}$$
	So half$=R(z^{(0)},\Phi(\Sigma,u_2^{(2)},\Phi(\chi_{odd},u_1^{(2)})))$.
	\medskip

	 \item $\min(x,y)$.

\sol  Notice that $\min(x,y)=y\mathring{-}(y\mathring{-}x)$: When $x\geq y$, $y\mathring{-}x=0$ so this expression is $0$. When $x<y$, $y\mathring{-}(y\mathring{-}x)=y-(y-x)=y-y+x=x$. Then
	$$\min=\Phi(\di,u_2^{(2)},\Phi(\di,u_2^{(2)},u_1^{(2)}))$$
\medskip

	 \item $\min^n(x_1,\dots,x_n)$ for all $n\geq 2$.

\sol  We proceed by recursion.
	$$\begin{array}{rcl}
		\min^n(x_1,\dots,0)	&=&	0=z^{(n-1)}(x_1,\dots,x_{n-1})\\
		&&\\
		\min^n(x_1,\dots,x_n+1)	&=&\left\lbrace\begin{array}{ll}
																			\min^n(x_1,\dots,x_n)	&	\textrm{ if }\min^n(x_1,\dots,x_n)\neq x_n\\
																			&\\
																			x_n+1							&	\begin{array}{l}
																												\textrm{ if }\min^n(x_1,\dots,x_n)= x_n\\
																												\wedge~\forall i\in\{1,\dots,n-1\},\ x_i\neq x_n
																												\end{array}\\
																			&\\
																			x_n								&	\begin{array}{l}
																												\textrm{ if }\min^n(x_1,\dots,x_n)= x_n\\
																												\wedge~\exists i\in\{1,\dots,n-1\},\ x_i=x_n
																												\end{array}

																			\end{array}\right.
	  \end{array}$$
	$$\hspace{-2cm}=\D(E(u_{n+1}^{(n+1)},u_n^{(n+1)})).u_{n+1}^{(n+1)}
		+E(u_{n+1}^{(n+1)},u_n^{(n+1)}).
		(u_n^{(n+1)}+
		\prod\limits_{i=1}^{n-1}\D(E(u_i^{(n+1)},u_n^{(n+1)})))(X^n,\min{\!}^n(X^n))$$
	$$\hspace{-2.9cm}=\underbrace{\Phi(\Sigma,\Phi(\Pi,\Phi(\D,\Phi(E,u_{n+1}^{(n+1)},u_n^{(n+1)})),u_{n+1}^{(n+1)}),
	\Phi(\Pi,\Phi(E,u_{n+1}^{(n+1)},u_n^{(n+1)}),\Phi(\Sigma,u_n^{(n+1)},g)))}_h(X^n,\min{\!}^n(X^n))$$
	where $X^n=(x_1,\dots,x_n)$ and $g$ is defined as follows
	$$g^{(n+1)}(X)=\prod\limits_{i=1}^{n-1} \D(E(u_i^{(n+1)},u_n^{(n+1)}))(X)=\Phi(\Pi,f_1,\Phi(\Pi,f_2,\dots,\Phi(\Pi,f_{n-2},f_{n-1})))(X)$$
	where $\forall i=1,\dots,n-1$, $f_i=\D(E(u_i^{(n+1)},u_n^{(n+1)}))$. Notice that $g$ is a well defined primitive recursive function since $n$ is fixed.

	Then $\min^n=R(z^{(n-1)},h)$.
	\medskip

	 \item $\max(x,y)$.

	\sol
	Notice that $\max(x,y)=x+(y\mathring{-}x)$: When $x\geq y$, $y\mathring{-}x=0$ so this expression is $x$. When $x<y$, $x+(y\mathring{-}x)=x+(y-x)=y$. Then
	$$\max=\Phi(\Sigma,u_1^{(2)},\Phi(\di,u_2^{(2)},u_1^{(2)}))$$
	\medskip

	 \item $rem(a,b)=$ remainder of the division of $a$ by $b$ (consider $rem(a,0)=a$).

	\sol We proceed by recursion, however we will do a recursion over $a$ instead of a recursion over $b$. Since the operator $R$ is defined for recursion over the last argument, we first define a function $rm(b,a)=$ remainder of the division of $a$ by $b$, and then we define $rem$ in terms of $rm$.
	$$\begin{array}{rcl}
		rm(b,0)&=&0 = z^{(1)}(b)\\
		rm(b,a+1)&=&(rm(b,a)+1).\D(E(rm(b,a)+1,b))\\
			&=& \Phi(\Pi,\Phi(s,u_3^{(3)}),\Phi(\D,\Phi(E,\Phi(s,u_3^{(3)}),u_1^{(3)})))(b,a,rm(b,a))
	  \end{array}$$
	Then $rm=R(z^{(1)},\Phi(\Pi,\Phi(s,u_3^{(3)}),\Phi(\D,\Phi(E,\Phi(s,u_3^{(3)}),u_1^{(3)}))))$

	Notice that $rem(a,b)=rm(b,a)$, then $rem=\Phi(rm,u_2^{(2)},u_1^{(1)})$.
	\medskip

	 \item $quo(a,b)=$ quotient of the division of $a$ by $b$, with $quo(a,0)=0$.

	\sol Again we want the recursion on the first argument, so we define $q(b,a)$ as the quotient of the division of $a$ by $b$.
	$$\begin{array}{rcl}
		q(b,0)		&=& 0=z^{(1)}(b)\\
		q(b,a+1) 	&=& q(b,a)+\D(rem(a+1,b))\\
						&=& \Phi(\Sigma,u_3^{(3)},\Phi(\D,\Phi(rem,\Phi(s,u_2^{(3)}),u_1^{(3)})))(b,a,q(b,a))
	  \end{array}$$
	Then $q=R(z^{(1)},\Phi(\Sigma,u_3^{(3)},\Phi(\D,\Phi(rem,\Phi(s,u_2^{(3)}),u_1^{(3)}))))$ and since $quo(a,b)=q(b,a)$, $quo=\Phi(q,u_2^{(2)},u_1^{(1)})$.
	\end{enumerate}
	\medskip

 \item Show that the following function is primitive recursive:
$$f(0)=0,\qquad f(1)=1,\qquad f(2)=2^{2^2},\qquad f(3)=3^{3^{3^3}}, \qquad\dots\qquad f(n)=n^{n^{\iddots^{\ n}}}\,(n\textrm{ times})$$

\sol Let $P(n,m)=n^{n^{\iddots^{\ n}}}\,(m\textrm{ times})$, then we define $P$ recursively as follows
$$\begin{array}{rcl}
	P(n,0)		&=& n = u_1^{(1)}(n)\\
	P(n,m+1)	&=& (P(n,m))^n = Exp(P(n,m),n)\\
					&=& \Phi(Exp,u_3^{(3)},u_1^{(3)})(n,m,P(n,m))
  \end{array}$$
 So, $P=R(u_1^{(1)},\Phi(Exp,u_3^{(3)},u_1^{(3)}))$. Now, notice that $f(n)=P(n,n)$, so $f=\Phi(P,u_1^{(1)},u_1^{(1)})$.

 \item Show that the following are recursive functions
	\begin{enumerate}
	 \item $f(x,y)=\lfloor\log_x y\rfloor$

	\sol Notice that $\log_x y = t \Rightarrow x^t=y$. Then $\lfloor\log_x y\rfloor=\min\{t~|~x^t\leq y\wedge x^{t+1}>y\}$. Also notice that the condition $x^t\leq y\wedge x^{t+1}>y$ can be rewritten as $x^t\mathring{-}y=0$ and $y\mathring{-}x^{t+1}=0$, or what is the same 
	$$(x^t\mathring{-}y)+(y\mathring{-}x^{t+1})=0$$
	Then let $f'(t,x,y)=(x^t\mathring{-}y)+(y\mathring{-}x^{t+1})$, so
	$$f'=\Phi(\Sigma,\Phi(\di,\Phi(Exp,u_2^{(3)},u_1^{(3)}),u_3^{(3)}),\Phi(\di,u_3^{(3)},\Phi(Exp,u_2^{(3)},\Phi(s,u_1^{(3)}))))$$
	And so, $f(x,y)=M[f'](x,y)$.
	\medskip

	 \item $g(x,y)=\lfloor\log_x y\rfloor+\lceil\sqrt[y]{x}\rceil$

	\sol Notice that $\sqrt[y]{x}=t\Rightarrow t^y=x$. Then $\lceil\sqrt[y]{x}\rceil=\min\{t~|~(t-1)^y\leq x\wedge t^y> x\}$. Also notice that the condition $(t-1)^y\leq x\wedge t^y> x$ can be rewritten as
	$$((t-1)^y\mathring{-}x)+(x\mathring{-}t^y)=0$$
	Then let $g'(t,x,y)=((t-1)^y\mathring{-}x)+(x\mathring{-}t^y)$, so
	$$g'=\Phi(\Sigma,\Phi(\di,\Phi(Exp,\Phi(Pd,u_1^{(3)}),u_3^{(3)}),u_2^{(3)}),\Phi(\di,u_2^{(3)},\Phi(Exp,u_1^{(3)},u_3^{(3)})))$$
	So $g=\Phi(\Sigma,f,M[g'])$.

	\medskip
	 \item $g(x,y)=\lceil\sqrt[4]{x+y}\rceil$

	\sol Notice that $\lceil\sqrt[4]{x+y}\rceil=\min\{t~|~(t-1)^4\leq x+y\wedge t^4> x+y\}$. Also notice that the condition $(t-1)^4\leq x+y\wedge t^4> x+y$ can be rewritten as
	$$((t-1)^4\mathring{-}(x+y))+((x+y)\mathring{-}t^4)=0$$
	Then let $h'(t,x,y)=((t-1)^4\mathring{-}(x+y))+((x+y)\mathring{-}t^4)$, so
	$$\begin{array}{rcl}
	   h'	&=&\Phi(\Sigma,
	\Phi(\di,
		\Phi(Exp,\Phi(Pd,u_1^{(3)}),four^{(3)}),
		\Phi(\Sigma,u_2^{(3)},u_3^{(3)})),\\
	&&\hspace{0.95cm}
	\Phi(\di,
		\Phi(\Sigma,u_2^{(3)},u_3^{(3)}),
		\Phi(Exp,u_1^{(3)},four^{(3)})))
	  \end{array}$$
	So $h=M[h']$
	\end{enumerate}
\medskip

 \item Show that the following function is recursive primitive.
	$$f(x,y)=\left\{\begin{array}{ll}
	                x+y & \textrm{ if }x\textrm{ is an even number, multiple of }3.\\
	                x\mathring{-}y & \textrm{ if }x\textrm{ is an odd number, multiple of }3.\\
					x & \textrm{ otherwise}.
	                \end{array}\right.$$

\sol $f(x,y)=\D(\D(rem(x,3))).(\chi_{even}(x).(x+y)+\chi_{odd}.(x\mathring{-}y))+\D(rem(x,3)).x$, so
$$\begin{array}{rcl}
f&=&\Phi(\Sigma,
				\Phi(\Pi,
						\Phi(\D,\Phi(\D,\Phi(rem,u_1^{(2)},three^{(2)}))),\\
						&&\hspace{1.9cm}\Phi(\Sigma,
								\Phi(\Pi,
									\Phi(\chi_{even},u_1^{(2)}),
									\Phi(\Sigma,u_1^{(2)},u_2^{(2)})),\\
						&&\hspace{2.85cm}\Phi(\Pi,
									\Phi(\chi_{odd},u_1^{(2)}),
									\Phi(\di,u_1^{(2)},u_2^{(2)})))),\\
				&&\hspace{0.95cm}\Phi(\Pi,\Phi(\D,\Phi(rem,u_1^{(2)},three^{(2)})),u_1^{(2)}))
\end{array}$$
\medskip

 \item Consider the following function:
	$$f(x,y)=\dfrac{x^2}{y}$$
	Is it recursive primitive? In such case, write it as so, in other case, write it as recursive function (if possible). Justify in any case.

\sol It is not recursive primitive because it is partial (it is not defined for $y=0$). We cannot write it for the general case, however we can approximate it with $\lfloor\dfrac{x^2}{y}\rfloor$.

Notice that $\lfloor\dfrac{x^2}{y}\rfloor=t\Rightarrow x^2\geq t.y\wedge (x+1)^2<t.y$, or what is the same $(t.y\mathring{-}x^2)+(x^2\mathring{-}t.y)=0$.

Then let $g(t,x,y)=(t.y\mathring{-}x^2)+(x^2\mathring{-}t.y)$, so
$$\hspace{-0.75cm}g=\Phi(\Sigma,
\Phi(\di,\Phi(\Pi,u_1^{(3)},u_3^{(3)}),\Phi(Exp,u_2^{(3)},two^{(3)})),
\Phi(\di,\Phi(Exp,\Phi(s,u_2^{(3)}),two^{(3)}),\Phi(\Pi,u_1^{(3)},u_3^{(3)})))$$
Then $f=M[g]$.

\subsection*{Extra}
 \item Give the complexity (big $\mathcal{O}$ notation) of the Turing machines at exercise 2 and of the simulation at exercise 1.

\sol \begin{description}
      \item[Exercise 1] Say the input of the machine to simulate is $n$ and its complexity is $N$. There is a number of steps at the beginning to set up the machine, which depends {\em linearly} of the size of $n$ (linearly since we have to copy the input ($n$) $k+1$ times, so we read and write  $(k+1).n$ times). At each move we do $k$ moves (one for head) and then $k.n$ to synchronize. So each move of the original machine takes $k+k.n$ moves of the new one. So, if the machine does in total $N$ movements, we will do $(k+k.n).N$ plus the $(k+1).n$ for the setting. So, the number of steps is $k.(n+1).N+(k+1).n$. If we consider $k$ fixed (i.e. a constant number), we can discard it and all the constants to take just the $\Oh$ notation, so we have $\Oh(n.N)$. That is, if the order of the original machine was $n^2$, the simulation will have an order $n^3$, and so on.
\medskip
	\item[Exercise 2]~
\begin{description}
 \item[Item (a)] $\Oh(1)$. Constant. It just takes 3 steps.
 \item[Item (b)] $\Oh(n)$. Lineal. It just passes through the tape once.
 \item[Item (c)] $\Oh(\infty)$. It never terminates.
 \item[Item (d)] $\Oh(n)$. Lineal. It do one passes and a half.
 \item[Item (e)] $\Oh(1)$. Constant. It just takes 3 steps.
 \item[Item (f)] $\Oh(n)$. Lineal. It runs a lineal machine and then a constant one.
\end{description}
 \end{description}
\end{enumerate}


\end{document}
