% 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}
\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 3: Decidability}
\author{Alejandro D\'iaz-Caro}
\date{2010}

\begin{document}
\begin{center}
 \textbf{\begin{large}Exercise sheet 5: Recursive functions\end{large}}
\end{center}

\begin{enumerate}
 \item Show that functions in $\RFF$ are total (\cf\ Theorem 18).
 \item Let $\{f_k~|~k\in\N\}$ be the set of Ackermann functions as saw in theory. Show that 
	$$\forall k\in\N,\ x>x'\Rightarrow f_k(x)>f_k(x')$$
 \item Define the following function as \RF. $f(x)=\lfloor\sqrt{x}\rfloor$
 \item Let $div(x,y)=\lfloor\frac{x}{y}\rfloor$. 
	\begin{enumerate}
	 \item Define the function $div$ as \RF, assuming $0/0=0$
	 \item Define the function $div$ as \RF, assuming $0/0$ is undefined.
	 \item Define $mod(x,y)$ which outputs the rest of the division of $x$ by $y$, as \RF using the definition of $div$.	
	\end{enumerate}
 \item Let $minus(x,y)=\left\{\begin{array}{ll}
	                    x	& \textrm{ if }y=0\\
						Pd(minus(x,Pd(y)))	& \textrm{ if }y\geq 1
	                    \end{array}\right.$.
	\begin{enumerate}
	 \item Calculate $f(4)$ where $f$ is defined as $\mu_y(minus(x,Pd(y)))$.
	 \item Is $f$ a total function or a parcial one?
	\end{enumerate}
 \item Prove that the function $f_0$ from the Ackermann sequence majorates all the basis function. ({\em cf.}~Theorem 20).
 \end{enumerate}

\end{document}
