% -----------------------acknowledge for overleaf and designer of this template-----------------------
\documentclass[12pt]{exam}
\usepackage{amsthm}
\usepackage{libertine}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{multicol}
\usepackage[shortlabels]{enumitem}
\usepackage{siunitx}
\usepackage{cancel}
\usepackage{graphicx}
\usepackage{pgfplots}
\usepackage{listings}


% automata
\usepackage{tikz}
\usetikzlibrary{automata, positioning, arrows}


\pgfplotsset{width=10cm,compat=1.9}
\usepgfplotslibrary{external}
\tikzexternalize

\newcommand{\class}{\Large Logic and Computation I, Autumn 2024 } % This is the name of the course 
\newcommand{\examnum}{Exercise 01-05} % This is the index of the homework
\newcommand{\examdate}{Due Date: } % This is the due date
\newcommand{\timelimit}{}





\begin{document}
\pagestyle{plain}
\thispagestyle{empty}

\noindent
\begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}} r @{\extracolsep{8pt}} l}
\textbf{\class} & & \textit{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}\\
&&\\
\textbf{\examnum} & &\textit{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}\\ 
\textbf{\examdate} &&\\
\end{tabular*}\\
\rule[2ex]{\textwidth}{2pt}
% ---


\noindent \textbf{Exercise 1.5.1}
Let  $\sigma(x,y)$ be a computable function. Prove the existence of computable function $g$ such that 
$$\{g(y) \}^n(x_1,  \cdots,x_n)  \sim  \{\sigma(g(y),y) \}^n(x_1,  \cdots,x_n).$$
Hint: Consider a computable function $h(x)$ such that $\{\{x \}(x)\} \sim \{h(x) \}$ and then $\sigma(h(x), y)$ is expressed as $\{S(y)\}(x)$ by the parameter theorem.
\bigskip

\noindent\underline{\textsf{Solution:}}

\vspace{10em}

\noindent \textbf{Exercise 1.5.2}
Show that the Ackermann function is not primitive recursive. \\
Hint: For any primitive recursive function $g(x, y)$ there exists a $c$ such that
$$g(x, y)<f(c, \max\{x, y \}).$$
\bigskip

\noindent\underline{\textsf{Solution:}}

\newpage

\noindent \textbf{Exercise 1.5.3 (Challenging)}

Show that the graph of the Ackermann function is a primitive recursive set.
\bigskip

\noindent\underline{\textsf{Solution:}}


\newpage

\noindent \textbf{Exercise 1.5.4 (Homework for everybody)}

Show that any infinite \textsf{CE} set contains an infinite computable subset. 
\bigskip

\noindent\underline{\textsf{Solution:}}

\end{document}



