% 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{\N}{\ensuremath{\mathbb{N}_0}}
\newcommand{\ie}{{\em i.e.}~}
\newcommand{\cf}{{\em cf.}~}
\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}}

\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}}
\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.
 \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$.
	 \item Construct a TM computing the zero function $z(X^k)=0$.
	 \item Construct a TM computing the empty function, \ie the function that is undefined for every $n\in\N$.
	 \item Construct a TM computing the projector $u_k^{(n)}(x_1,\dots,x_k,\dots,x_n)=x_k$.
	 \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.$
	 \item Using sequential composition, construct a TM computing the constant function $one$.\\
	Tip: $one=\Phi(s^{(1)},z^{(n)})$.
	\end{enumerate}

\subsection*{Primitive recursive functions}
 \item Let $\lessdot$ be a primitive recursive relation. Show that the following functions are primitive recursive.
	\begin{enumerate}
	 \item $f_1(x,y_0,y)=$ the first value $z$ in $[y_0,y]$ for which $x\lessdot z$.
	 \item $f_2(x,y)=$ the second value $z$ in $[0,y]$ for which $x\lessdot z$.
	 \item $f_3(x,y)=$ the largest value $z$ in $[0,y]$ for which $x\lessdot z$.
	\end{enumerate}
	If there is not value $z$ in the range such that $x\lessdot z$, then $f_i$ is $y+1$.
 \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.$$
 \item Give primitive recursive definitions for the following functions
	\begin{enumerate}
	 \item half$(x)=\lfloor\dfrac{x}{2}\rfloor$.
	 \item $\min(x,y)$.
	 \item $\min^n(x_1,\dots,x_n)$ for all $n\geq 2$.
	 \item $\max(x,y)$.
	 \item $rem(a,b)=$ remainder of the division of $a$ by $b$.
	 \item $quo(a,b)=$ quotient of the division of $a$ by $b$, with $quo(a,0)=0$.
	\end{enumerate}
 \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})$$
\subsection*{Recursive functions}
 \item Show that the following are recursive functions
	\begin{enumerate}
	 \item $f(x,y)=\lfloor\log_x y\rfloor$
	 \item $g(x,y)=\lfloor\log_x y\rfloor+\lceil\sqrt[y]{x}\rceil$
	 \item $g(x,y)=\lceil\sqrt[4]{x+y}\rceil$
	\end{enumerate}
\subsection*{Mixed}
 \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.$$
 \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.
\end{enumerate}

\end{document}
