\documentclass[11pt]{amsart}

\usepackage{amsmath,amsthm,amssymb}
\usepackage{stmaryrd}

\usepackage{fancyhdr} % Allows customization of verbatim environments

\usepackage{xcolor}

%\usepackage[textheight=8.5in, margin=1.6in]{geometry}
\usepackage[
  hmarginratio={1:1},     % equal left and right margins
%  vmarginratio={1:1},     % equal top and bottom margins
  %textwidth=400pt,        % new text width
  heightrounded,          % always useful
  %bindingcorrection=5mm,  % binding correction
  total={6in,8in}
]{geometry}
\headheight=13pt
\footskip=13pt

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage{graphicx}

% Tikz stuff.
\usepackage{tikz}
%\usepackage{tkz-graph}
\usepackage{pgfplots}
%\usepackage{tikz-3dplot}
\pgfplotsset{compat=newest}
%\usepgfplotslibrary{fillbetween}
%\usetikzlibrary{cd}
%\usetikzlibrary{positioning}
%\usetikzlibrary{decorations.pathmorphing}    
%\usetikzlibrary{decorations.pathreplacing}
%\usetikzlibrary{arrows.meta,calc}
%\usetikzlibrary{bending}
%\usetikzlibrary{decorations.markings,shapes.geometric}
%\tikzset{->-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{>}}},postaction={decorate}}}
%\tikzset{-|-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{stealth}}},postaction={decorate}}}
%\tikzset{movearrow/.style 2 args ={
%        decoration={markings,
%	  mark= at position {#1} with {\arrow{#2}} ,
%        },
%        postaction={decorate}
%    }
%}
%\tikzset{<--/.style={decoration={markings, mark=at position #1 with
%  {\arrow{<}}},postaction={decorate}}}
\tikzstyle{ball} = [circle,shading=ball, ball color=black,
    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{bball} = [circle,shading=ball, ball color=blue,
%    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{miniball} = [circle,shading=ball, ball color=black,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{redminiball} = [circle,shading=ball, ball color=red,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{mminiball} = [circle,shading=ball, ball color=black,
%    minimum size=0.6mm,inner sep=0.1pt]
%\tikzstyle{mycircle} = [draw,circle, minimum size=1mm,inner sep=1.3pt]
%\newcommand*{\DashedArrow}[1][]{\mathbin{\tikz [baseline=-0.25ex,-latex, dashed,#1] \draw [#1] (0pt,0.5ex) -- (1.3em,0.5ex);}}%

%%%% tikz style for finite automata
\usetikzlibrary{automata, positioning, arrows}
\tikzset{fa/.style={
    ->, % makes the edges directed
    >=stealth, % makes the arrow heads bold
    node distance=3cm, % specifies the minimum distance between two nodes. Change if necessary.
    every state/.style={thick, fill=gray!10}, % sets the properties for each ’state’ node
    initial text=$ $, % sets the text that appears on the start arrow
}}
%%%%

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage[shortlabels]{enumitem}
\setlist[enumerate]{itemsep=4pt,leftmargin=*,label={(\alph*)}}
%\setlist[enumerate]{itemsep=2pt,label={\arabic*.}}

\usepackage[T1]{fontenc}
\renewcommand{\labelitemi}{\guillemotright}

\allowdisplaybreaks

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\KK}{\Bbbk}
\newcommand{\ve}{\varepsilon}
\newcommand{\scribe}{
  \begin{center}%
    Scribe~$=$ \rule{7cm}{0.15mm}%
  \end{center}%
  \medskip%
}
\DeclareMathOperator{\im}{\mathrm{im}}
\DeclareMathOperator{\id}{\mathrm{id}}
\DeclareMathOperator{\glb}{\mathrm{glb}}
\DeclareMathOperator{\lub}{\mathrm{lub}}

\newcounter{problem}
\renewcommand \thesection {\theproblem}
\newenvironment{prob}[1][]
{
\refstepcounter{problem}\par\medskip
\def\myArg{#1}
  \ifx\myArg\empty
    \noindent \textsc{Problem~\theproblem.} \rmfamily
  \else
    \noindent \textsc{Problem~\theproblem\ (\textnormal{#1}).} \rmfamily
  \fi
}
{
\medskip

}

\newenvironment{sol}
{\emph{Solution.}
}
{
  \medskip

}

\parskip = 0.05in
\parindent = 0.0in

%\pagestyle{empty}
%\pagenumbering{gobble}

\fancypagestyle{firststyle}
{
\fancyhead[L,LO]{
\textit{\small Math 387 Group problems, Wednesday Week 3}
}
\renewcommand{\headrulewidth}{0pt}
}

\begin{document}
\thispagestyle{firststyle}

\bigskip

\begin{prob}
  Let an $n$-PDA be a PDA with $n$ stacks.
  \begin{enumerate}
    \item Why is a $1$-PDA more powerful than a $0$-PDA?
    \item What word would you use to prove that the language
      $L:=\{a^{n}b^{n}c^{n}: n \geq 0\}$ is not context free.  Say $p$ is a
      pumping length for a posited PDA. No explanation necessary.
    \item Prove that a $2$-PDA more powerful than a $1$-PDA.  Give a specific
      example, and describe the relevant $2$-PDA using numbered steps describing
      in English the action of the machine.  You do not need to
      draw a state diagram.
  \end{enumerate}
  It turns out that $n$-PDAs for $n\geq2$ have the same power as Turing machines! That's
  something to think about after completing the rest of today's problems.
\end{prob}

\begin{prob}
  Review the concept of an enumerator.
  Let $\Sigma=\{0,1\}$. \emph{Standard string order} on $\Sigma^{*}$ means
  ordering strings in increasing length and ordering
  strings of the same length in \emph{lexicographic order} taking $0<1$:
  \[
    \varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, \ldots
  \]
  Show that a language~$L$ is Turing decidable if and only if some enumerator
  enumerates the language in standard string order.  
\end{prob}

\begin{prob}
  \begin{enumerate}
    \item Draw the state machine for a TM that takes as input a word of the form
      $w\#v$ where $w,v\in \{0,1\}^{*}$, and outputs $w$\textvisiblespace$\#v$.
      Notate your transitions as in the text.  For example, 
      \[
	q_{1}\xrightarrow{0\to 1, R}q_{2} 
      \]
	means that if the machine is in state $q_{1}$ and the head reads a $0$, then it
	writes a~$1$, moves the head to the right, and moves to state~$q_{2}$.
	There is also a shorthand notation,
	\[ 
	  q_{1}\xrightarrow{0\to R}q_{2} 
	\] 
	means that if the machine is in state $q_{1}$ and the head reads a $0$, then it writes a~$0$, moves the
	head to the right, and moves to state~$q_{2}$. 
      \item Trace the set of configurations your TM moves through starting with
	the input $001\#10$.  Use the notation from the book, e.g., $11q_{2}01$
	means machine is in state~$q_{2}$ and the head is reading a~$0$.
  \end{enumerate}
\end{prob}

\begin{prob}
  \begin{enumerate}
    \item List all binary strings of length at most~$4$ in standard order:
      $\varepsilon, 0, 1, 00, 01, \ldots$
    \item Describe an enumerator that prints words in $\Sigma=\{0,1\}$ in
      standard string order.  Your enumerator is a TM but with a print command
      which, when called, prints the contents of the tape from the beginning to
      the first blank cell.  Your solution should again be a list of steps with
      descriptions in English.  You do not need to produce a state diagram.
  \end{enumerate}
\end{prob}

\begin{prob}
  Let $D$ be the set of polynomials $p$ in $n$ variables and integer
  coefficients such that $p(x_{1},\ldots,x_{n})=0$ has a solution
  $a=(a_{1},\ldots,a_{n})\in \Z^{n}$.  Why is $D$ Turing recognizable? You need
  to describe a Turing machine that halts (after a finite number of steps) if
  and only if there is a solution. Recall that Hilbert's tenth question is,
  essentially, whether~$D$ is Turing \emph{decidable}.
\end{prob}

\end{document}
