%
% 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 2023}
\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, December 2 at 2:30 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}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Two, part ii. here.
    \end{shaded}

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

\newpage


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

\section*{Problem Five: What Does it Mean to Solve a Problem?}
    i.
    \begin{shaded}
    Write your answer to Problem Five, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Five, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Five, part iii. here.
    \end{shaded}
    
    iv.
    \begin{shaded}
    Write your answer to Problem Five, 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}