%---------------------------------------------------------------------------
% Time-stamp: <2023-10-12 11:28:20 sutner>  
%
%  File:	midterm-17.tex
%  Purpose:	CDM midterm, Fall 2023
%
%---------------------------------------------------------------------------
\documentclass[12pt]{ks-exam}

\usepackage{ks-texmacs}
\usepackage{xcolor}
\usepackage{hyperref}

% \listfiles

%---------------------------------------------------------------------------
% customization
% 

\def\coursename{15-354}
\def\examtype{Midterm}

% \def\arrstr{1}
% \setlength{\stwidth}{30mm}

\parskip 1ex
\parindent 0mm

\Mathsf{sync}
\Mathsf{fac}
\Mathcal{L}
\Mathcal{A}
\Mathcal{B}
\def\O{\mathit{O}}
\def\SS{\Sigma^{*}}

\def\tblu#1{\textcolor{blue}{#1}}
\let\emph=\tblu

\let\separator=\newpage

%----------------------------------------------------------------------
\begin{document}


\begin{minipage}[t]{2.6in}
\vspace*{3ex}

{\LARGE\bfseries \coursename: \examtype}
\vspace{2ex}

\textbf{Thursday, October 12, 2023}
\end{minipage}

\vspace{10ex} 

\textbf{Instructions}

\begin{itemize}
\addtolength{\itemsep}{2mm}
\item  You have until Friday, 10/13, 16:00, to work on this test. 

\item  The latex source is at 
\href{http://www.cs.cmu.edu/~cdm/resources/midterm-23.tex}{midterm-23.tex}.
Your can type your answers directly into this file, but make sure to change the file name to 
\texttt{FirstnameLastname.tex}. 
To compile, you also need to download 
\href{http://www.cs.cmu.edu/~cdm/resources/ks-exam.cls}{ks-exam.cls} and 
\href{http://www.cs.cmu.edu/~cdm/resources/ks-texmacs.sty}{ks-texmacs.sty}.

\item  When you are done, email your pdf to me at \texttt{sutner@cs.cmu.edu}. 
\item  You can consult all course materials, but no other sources.
\item  Do not talk to anyone about this exam. 
\item  Post questions to ed, but make your posts private (unless it's about a typo or the like). 
\item  Good luck. 
\end{itemize}

\newpage

%---------------------------------------------------------------------------
\titledquestion{Multiple Choice}{24}

Answer each of the following questions \textbf{true} or \textbf{false}, 
no justification is necessary. 

\begin{enumerate}
\addtolength{\itemsep}{2mm}

\item  
Suppose $A, B \subseteq \N$ and the symmetric difference between $A$ and $B$ is finite.
Show that $A$ is decidable whenever $B$ is decidable.
\vspace{1ex} 

Answer: 

\item  
Wurzelbrunft thinks he has a miraculous proof that every recursively enumerable
set can be enumerated by a computable function $f$ that is almost monotonic:
$f(n) \geq f(m) - 42$ for all $n \geq m$.
Is he right? 
\vspace{1ex} 

Answer: 

\item  
Suppose we compute a primitive recursive function on a register machine.
Is the running time of the register machine always primitive recursive?
\vspace{1ex} 

Answer: 

\item  
Let $L \subseteq \Star{a}$ be an infinite regular language. 
Is there always an infinite subset of $L$ of the form $a^{k} \Star{(a^{\ell})}$
for some $k \geq 0$, $\ell \geq 1$?
\vspace{1ex} 

Answer: 

\item  
Does every infinite regular language $L \subseteq \Star{a}$ have an 
undecidable subset?
\vspace{1ex} 

Answer: 

\item  
Suppose $L \subseteq \Star{a}$ is an  infinite regular language. 
Are there always two disjoint infinite regular languages 
$K_{1}, K_{2} \subseteq L$?
\vspace{1ex} 

Answer: 

\item  
Suppose a set $A \subseteq \N$ is enumerated by a computable function. 
Is is it always true that the set can also be enumerated by 
a primitive recursive function? 
\vspace{1ex} 

Answer: 

\item  
Let $L \subseteq \SS$ be a decidable language.
Is the Kleene star of $L$ is also decidable?
\vspace{1ex} 

Answer: 

\end{enumerate} 

\separator

%---------------------------------------------------------------------------
\titledquestion{Register Complexity}{16}

Let us say a register $R$ in a register machine is \emph{useful} if it is an 
input/output register or 
there is some input $\vec{x}$ such that, during the computation on $\vec{x}$, 
the register $R$ changes its value at least once. 
The whole machine is \emph{trim} if all its registers are useful. 

Justify your answer for both questions below.  

\begin{Enumerate}
\item  Is it true that register machines with at most $1024$ registers
cannot implement all computable functions $\N\to\N$? 

\item  Is it decidable whether a register machine is trim?
\end{Enumerate}

\separator

%---------------------------------------------------------------------------
\titledquestion{Wurzelbrunft and Ochsenfiesl vs. Collatz}{20}

Wurzelbrunft and Ochsenfiesl are two grad students at a little known 
university in a galaxy far, far away.   
They both are fascinated by the Collatz function 
$C(x) = x/2$ for $x$ even, and $C(x) = 3x+1$ otherwise.
The Collatz Conjecture says that all orbits of $x \geq 1$ under $C$ 
contain the point 1.
This has been verified numerically for $x < 2^{68}$ and there are some 
interesting theorems about $C$, but the conjecture is wide open% 
\footnote[1]{Jeff Lagarias has written a book on the problem, and 
thinks it's harder than the Riemann hypothesis.}.

At any rate, Wurzelbrunft and Ochsenfiesl decided to study the complexity 
of the \emph{Collatz set}
$$
      S = \set{ x \in \N_{+} }{ \text{ orbit of $x$ under $C$ contains 1}}.
$$
Wurzelbrunft thinks he has a proof that $S$ is decidable. 
He also claims that his result, together with the well-known fact 
that $S$ is infinite, immediately implies the Collatz conjecture. 
Ochsenfiesl, on the other hand, thinks he has a proof that $S$ is 
undecidable.  He claims his result implies that the Collatz conjecture 
is false. 

If you were their PhD advisor, 
what professional, well-reasoned advice would you give to them? 

\begin{Enumerate}
\item  Wurzelbrunft: 
  
\item  Ochsenfiesl:

\end{Enumerate}

\separator

%---------------------------------------------------------------------------
\titledquestion{Speedy Iteration}{20}

Suppose a function $\func{f}{[n]}{[n]}$ is given as a lookup table, 
say, a plain array of integers. 
Think about $n$ as being fairly large, somewhere between $2^{20}$ and $2^{30}$.
Clearly we can compute $f^t(x)$, $x \in [n]$, $t \geq 0$, by repeated lookup. 
This problem is about speeding up this computation. 

The pre-computation in part (B) can store additional information, but 
make sure to use sub-quadratic space. 


\begin{Enumerate}
\item  Explain how to reduce the problem of computing $f^{t}(x)$,  
to the problem of computing only values $f^{t'}(x)$ for $t' < n$. 

\item  Now assume that we need to perform many computations of various values 
$f^{t}(x)$. 
Show how to organize a pre-computation that speeds up these queries. 

\item State clearly the cost of the pre-computation (time and space) and the 
improved evaluations. 
\end{Enumerate}

\separator

%---------------------------------------------------------------------------
\titledquestion{Factors}{20}

A word $u$ is a factor of a word $v$ if $v = xuy$ for some words 
$x,y \in \SS$. 
Write $\fac(L)$ for the language of all factors of a language $L$. 
For example, for the even/even language $EE$ over $\setof{a,b}$
we have $\fac(EE) = \Star{\setof{a,b}}$.

In part (A), do not use any nondeterministic machines. 
Try to make your algorithms below as simple as possible, but don't 
worry about efficiency. 

\begin{Enumerate}
\item Let $\cA$ be the minimal DFA for $L$. 
Explain how to construct a DFA for $\fac(L)$. 
\item  Let $\cB$ be some NFA for $L$. 
Explain how to construct an NFA for $\fac(L)$. 
\end{Enumerate}

\end{document}
%---------------------------------------------------------------------------


% LocalWords:  pdf Ochsenfiesl Lagarias xuy tex FirstnameLastname texmacs EE
