%---------------------------------------------------------------------------
% Time-stamp: <2024-10-10 11:05:49 sutner>  
%
%  File:	midterm-24.tex
%  Purpose:	CDM midterm, Fall 2024
%
%---------------------------------------------------------------------------
\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 10, 2024}
\end{minipage}

\vspace{10ex} 

\textbf{Instructions}

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

\item  The latex source is at 
\href{http://www.cs.cmu.edu/~cdm/resources/midterm-24.tex}{midterm-24.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. 
\vspace{2ex} 
 
\begin{enumerate}
\addtolength{\itemsep}{4mm}

\item  
Wurzelbrunft thinks he has found a clone of total arithmetic functions that is 
somewhat difficult to describe (his paper is 120 pages long), but it captures 
intuitive computability perfectly. 
Could he be right? 
\vspace{1ex} 

Answer: 


\item Imagine someone hands you a BlackBox that somehow solves the  
Halting problem.
Could one use this device to decide whether a computable function is total?
\vspace{1ex} 

Answer:

\item  
Suppose a set $A \subseteq \N$ is decidable. Is is it always true that 
there is a primitive recursive decision algorithm for $A?$ 
\vspace{1ex} 

Answer: 


\item  
Suppose $L \subseteq \SS$ is an infinite regular language. 
Is it always possible to partition $L$ into two infinite regular languages?
\vspace{1ex} 

Answer: 

\item  
Is there an infinite language $L \subseteq \Star{\setof{a}}$ that has no infinite regular
sub-language? 
\vspace{1ex} 

Answer: 

\item  
Let $L \subseteq \Star{\setof{a}}$ be an undecidable language.
Is the Kleene star of $L$ always undecidable?
\vspace{1ex} 

Answer: 

\end{enumerate} 

\separator

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

Let us say a register $R$ in a register machine is \emph{bounded} if there is some 
fixed bound $B$ such that during the computation on some arbitrary input the value
stored in $R$ is never larger than $B$. 
Two registers $R_{1}$ and $R_{2}$ are \emph{entangled} if, at the end of every 
halting computation, they have the same value. 

Justify your answer for both questions below.  

\begin{Enumerate}
\item  Is it decidable whether a register is bounded? 

\item  Is it decidable whether two registers are entangled?
\end{Enumerate}

\separator

%---------------------------------------------------------------------------
\titledquestion{Wurzelbrunft Functions}{30}

Someone has given Wurzelbrunft a recursion theory book on his birthday.
He finds large function values produced by monsters such as the Ackermann function
confusing, so he decides to study \emph{$k$-Wurzelbrunft} functions:
any total computable function
$\func{f}{\N}{\N}$ such that $f(x) < k$ for all $x$.  Here $k \in \N$.

Wurzelbrunft thinks that, for sufficiently small $k$, all $k$-Wurzelbrunft
functions are primitive recursive.
Help him come up with an actual theorem and a proof.
The stronger the theorem, the better.

\begin{Enumerate}
  \addtolength{\itemsep}{2mm}
\item   Clearly state your $k$-Wurzelbrunft theorem.
\item   Prove your theorem.
\end{Enumerate}

\separator

%---------------------------------------------------------------------------
\titledquestion{$A$-RMs}{40}

\Background

Fix some set $A \subseteq \N$.
Suppose we modify a register machine by adding a an instruction \texttt{magicA k l}
which executes as follows: the machine reads the number $r$ in register $R_{0}$.
Then it magically figures out whether $r$ is in $A$; if so,
execution continues in line $k$, and in line $l$ otherwise.

Call these gizmos \emph{$A$-RMs}.

\Task

\begin{Enumerate}
\addtolength{\itemsep}{2mm}
\item  Show that all $A$-RMs can be simulated by an ordinary RM iff $A$ is decidable.
\item  For any $A$, construct a set $H$ that cannot be decided by any $A$-RM.
\item  Suppose you have access to a $H$-RM where $H$ is the Halting set (for ordinary RMs).
  Explain how to exploit this to prove or disprove the Goldbach conjecture:
  every even number larger than 2 is the sum of two primes.
\end{Enumerate}

\separator

%---------------------------------------------------------------------------
\titledquestion{Computing Transients and Periods}{20}

For the following, assume we are given a \Cee program that computes
a function $\func{f}{A}{A}$ where $A = \setof{0,1,\ldots,2^{64}-1}$ 
(64-bit unsigned ints).
Assume that the computation of $f(a)$ is expensive (though, by 
necessity ).

Write $t$ for the \emph{transient} of a point in $A$, and $p$ for the \emph{period}.
We can compute $t$ and $p$ in a memoryless way using Floyd's algorithm,
but sometimes there are better solutions.
If you write pseudo-code to describe your algorithms below, make sure to
provide ample comments; no credit otherwise.
\vspace{1ex}

\begin{Enumerate}
\item   Suppose that the transients of all points under $f$
are at most 3 (three).
Give a fast and memory efficient algorithm to compute the
transient and period of a point $a \in A$.
State the running time of your algorithm in terms of $t$ and $p$
(try to spell out the constants).
\vspace{2ex} 

\item   Now suppose that the periods of all points under $f$
are at most 3 (three).
Give a fast and memory efficient algorithm to compute the transient and
period of a point $a \in A$.
State the running time of your algorithm in terms of $t$ and $p$
(try to spell out the constants).
\end{Enumerate}

\separator

%---------------------------------------------------------------------------
\titledquestion{Word Shuffle}{30}

\def\shuff{\mathop{\Vert}}
\def\shuffle{\mathsf{sh}}


The \emph{word shuffle} operation, in symbols $\shuff$, is a map from
$\SS \times \SS$ to $\fP(\SS)$ defined by
%
\begin{align*}
  \eps \shuff y &= y \shuff \eps\ =\ \{ y\}  \\
  xa \shuff yb  &= (x \shuff yb)\,a \cup (xa \shuff y)\,b.
\end{align*}
%
As usual, we can extend the operation to languages by
$$
     K \shuff L = \bigcup \set{ x \shuff y }{ x \in K, y \in L}
$$
For example,
$$
aa \shuff bbb =
\setof{aabbb, ababb, abbab, abbba, baabb, babab, babba, bbaab, bbaba, bbbaa}
$$
Also, $\Star{(aa)} \shuff \Star{(bb)}$ is the set of all even/even words.

\begin{Enumerate}
  \addtolength{\itemsep}{2mm}
\item  Given two words $x$ and $y$, construct a finite state machine $M$
  that accepts $x \shuff y$.

\item  Let $M_{i} = \struct{Q_{i},\Sigma,\delta_{i}; q_{0i},F_{i}}$, $i=1,2$,
  be two DFAs accepting regular languages $L_{i}$.
Show how to construct a finite state machine $M$ that accepts the shuffle language
$L_{1} \shuff L_{2}$.
Make sure to specify the state set, the transitions, initial and final states.
\end{Enumerate}

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


% LocalWords:  pdf Ochsenfiesl Lagarias xuy tex FirstnameLastname texmacs EE
