%
% LaTeX Problem Set Template originally designed
% by former CS103 TA Sachin Padmanabhan, with updates,
% edits, and simplifications by the lovely folks below.
%
% Updated for Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd
% Updated for Fall 2020 by Lucy Lu
% Updated for Winter/Spring 2021 by Cynthia Bailey Lee
% Updated for Fall 2021 by Grant McClearn
% Commands slimmed down and simplified in Fall 2022 by Keith Schwarz

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage{braket}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{hyperref}
\usepackage{wrapfig}
\usepackage{mathrsfs}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,
    urlcolor=blue,
}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#8}
\author{[TODO: Replace this with your name(s)]}
\date{\today}

% Running author based on https://tex.stackexchange.com/questions/68308/how-to-add-running-title-and-author#answer-68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set 8}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2024}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\powerset}[1]{\wp\left(#1\right)}
\newcommand{\suchthat}{\ \vert \ }
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\reals}{\mathbb{R}}
\renewcommand{\qed}{\blacksquare}
\newcommand{\accepts}{\text{ accepts }}
\newcommand{\rejects}{\text{ rejects }}
\newcommand{\loopson}{\text{ loops on }}
\newcommand{\haltson}{\text{ halts on }}
\newcommand{\encoded}[1]{\left\langle#1\right\rangle}
\newcommand{\rlangs}{\mathbf{R}}
\newcommand{\relangs}{\mathbf{RE}}
\newcommand{\corelangs}{\text{co-}\mathbf{RE}}
\newcommand{\plangs}{\mathbf{P}}
\newcommand{\nplangs}{\mathbf{NP}}

\renewcommand{\labelitemii}{$\bullet$}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{mdframed}
\usepackage{float}

\makeatother

\definecolor{shadecolor}{gray}{0.95}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parindent}{0pt}

\pagestyle{fancy}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\usepackage{boxedminipage}
\newenvironment{blank}{\colorbox{shadecolor}{\strut \underline{\ \ \ \ \ }}}

\begin{document}

\maketitle

\begin{center}
  \emph{Due Friday, March 8 at 4:00 pm Pacific}
\end{center}

You'll submit your answers to Problem 1 and Problem 4 separately.

Symbols you might find helpful in this problem set:

\begin{itemize}
    \item The "unstar" of a monoid from Q3 is written $M^\dagger$.
\end{itemize}

\pagebreak

\section*{Problem Two: The Fixed-Point Theorem}
    i.
    \begin{shaded}
    Write your answer to Problem Two, part i. here.
    \end{shaded}

    \newpage
    
    ii.
    \begin{shaded}
    Write your answer to Problem Two, part ii. here.
    \end{shaded}

    \newpage

    iii.
    \begin{shaded}
    Write your answer to Problem Two, part iii. here.
    \end{shaded}

    \newpage
    
    iv.
    \begin{shaded}
    Write your answer to Problem Two, part iv. here.
    \end{shaded}

\newpage

\section*{Problem Three: Unstarring a Language}
    i.
    \begin{shaded}
    Write your answer to Problem Three, part i. here.
    \end{shaded}

    \newpage

    ii.
    \begin{shaded}
    1. Write your answer to Problem Three, part ii., question 1 here. \\
    2. Write your answer to Problem Three, part ii., question 2 here. \\
    3. Write your answer to Problem Three, part ii., question 3 here. \\
    4. Write your answer to Problem Three, part ii., question 4 here. 
    \end{shaded}

    \newpage
    
    iii.
    \begin{shaded}
    Write your answer to Problem Three, part iii. here.
    \end{shaded}

\newpage

\section*{Problem Five: Executable Computability Theory}
    i.
    \begin{shaded}
    \begin{itemize}
    \item Write your answer to Problem Five, part i., first bullet point here.
    \item Write your answer to Problem Five, part i., second bullet point here.
    \item Write your answer to Problem Five, part i., third bullet point here. 
    \end{itemize}
    \end{shaded}

    \newpage
    
    ii.
    \begin{shaded}
    \begin{itemize}
    \item Write your answer to Problem Five, part ii., first bullet point here.
    \item Write your answer to Problem Five, part ii., second bullet point here.
    \item Write your answer to Problem Five, part ii., third bullet point here. 
    \end{itemize}
    \end{shaded}

    \newpage
    
    iii.
    \begin{shaded}
    \begin{itemize}
    \item Write your answer to Problem Five, part iii., first bullet point here.
    \item Write your answer to Problem Five, part iii., second bullet point here.
    \item Write your answer to Problem Five, part iii., third bullet point here. 
    \end{itemize}
    \end{shaded}
    
\newpage

\section*{Problem Six: What Does it Mean to Solve a Problem?}
    i.
    \begin{shaded}
    Write your answer to Problem Six, part i. here.
    \end{shaded}

    \newpage
    
    ii.
    \begin{shaded}
    Write your answer to Problem Six, part ii. here.
    \end{shaded}

    \newpage
    
    iii.
    \begin{shaded}
    Write your answer to Problem Six, part iii. here.
    \end{shaded}

    \newpage
    
    iv.
    \begin{shaded}
    Write your answer to Problem Six, part iv. here.
    \end{shaded}
    
\newpage

\section*{Optional Fun Problem: TMs and Regular Languages}
\begin{shaded}
Write your answer to the Optional Fun Problem here.
\end{shaded}

\end{document}