\documentclass[]{article}
% Required packages.
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{color}
\usepackage{tikz}
\usepackage[utf8]{inputenc}
\usepackage{dsfont}
\usepackage{enumerate}
\let\mathbb\mathds
% Some setup.
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\setcounter{secnumdepth}{0}
% Input data macros for \maketitle.
\title{CS 4810: Homework 5}
\author{due 10/11 11:59pm}
\date{(your name + netid)} % TODO: Fill in your own name and netID here.
\sloppy
% The actual document technically begins here.
\begin{document}
\maketitle
Collaborators: (names and netids) % TODO: List the names and netIDs of everyone who collaborated with you on this homework here.
Each problem is worth 25 points.
\section{Problem 1}
Show that there exists a Turing machine that on input $01^i01^j0$ outputs
$01^{i \cdot j}0$ for all $i,j\in \mathbb N$.
Describe how the Turing machine operates on the tape for a given input $01^i01^j$.
\bigskip
In all following problems, you may assume that there similarly exist Turing machines that compute other basic arithmetic and control-flow operations, such as addition, if-then-else, and while loops.
You may therefore provide pseudocode whenever a description of a Turing machine is requested.
\section{Problem 2}
\begin{enumerate}[a.]
\item Show that there exists a Turing machine to decide if the language of a
deterministic finite automaton is empty. In other words, show that the
following lanugage is decidable,
\begin{displaymath}
L_1=\{\langle A \rangle \mid \text{$A$ is a DFA with $L(A)=\emptyset$}\}.
\end{displaymath}
\item Show that there exists a Turing machine to decide given two DFAs
$A$ and $B$ if the language of $A$ contains the language of $B$.
In other words, show that the following language is decidable,
\begin{displaymath}
L_2 = \{ \langle A, B \rangle \mid \text{$A$ and $B$ are DFAs with $L(A)\subseteq L(B)$ } \}.
\end{displaymath}
\emph{Hint:} Use closure properties of regular languages to reduce
$L_2$ to $L_1$.
\end{enumerate}
\section{Problem 3}
\sloppy
Show that the following languages are undecidable.
You may use Rice's theorem if it applies or you may reduce from the acceptance problem $\mathrm{A}_{\mathrm{TM}}$ for Turing machines.
\begin{enumerate}[a.]
\item
\begin{align*}
% \begin{aligned}[b]
L_1 = \{ \langle M, w\rangle \mid
& \text{ $M$ is a single-tape TM that never modifies the portion}\\
& \text{ of the tape that contains the input $w$} \},
% \end{aligned}
\end{align*}
\item
\begin{align*}
L_2 = \{ \langle M \rangle \mid \text{$M$ is a TM and $L(M) = \Sigma^\ast$}\}.
\end{align*}
\end{enumerate}
\section{Problem 4}
We say a function $f:\mathbb N \to \mathbb N$ is \emph{computable} if
there exists a Turing machine $M$ that on input $1^n$ outputs$^1$ $1^{f(n)}$.
(You may assume that $M$ has tape alphabet $\{0,1,\square\}$.)
A \textit{busy beaver} with $n$ states is a Turing machine with tape alphabet $\{0,1,\square\}$, which on input $\varepsilon$ outputs\footnote{Recall that we say that a Turing machine $M$ on input $w$ \emph{outputs} a string $w'$ if $M$ halts with just $w'$ written on the tape.} a string of as many 1s as possible (among all such Turing machines with $n$ states).
For $n\in\mathbb N$, let $\mathrm{BB}(n)$ be the number of 1s a busy beaver with $n$ states can produce.
\begin{enumerate}[a.]
\item
Prove that $\mathrm{BB}$ is nondecreasing, i.e. $\mathrm{BB}(m)\ge \mathrm{BB}(n)$ if $m\ge n$.
\item
Argue that for every computable function $f$, there exists a constant $c\in \mathbb N$ such that $\forall n\in\mathds{N}.\,\mathrm{BB}(c+n)\geq f(\mathrm{BB}(n))$.
\item
Show that $\mathrm{BB}(n)\geq 2\cdot n -d$ for some constant $d\in \mathbb N$.
\item
Hence conclude that $\mathrm{BB}(n)$ is not computable.
\end{enumerate}
\emph{Remark:} Each of the four parts has a short answer.
\end{document}