\documentclass[12pt]{article} \usepackage{amsmath} \usepackage{comment} \newcommand{\INF}{{\rm INF }} \newcommand{\HALT}{{\rm HALT }} \newcommand{\ACC}{{\rm ACC }} \newcommand{\REG}{{\rm REG }} \newcommand{\DFA}{{\rm DFA }} \newcommand{\NFA}{{\rm NFA }} \newcommand{\DCFG}{{\rm DCFG }} \newcommand{\CFG}{{\rm CFG }} \newcommand{\CFL}{{\rm CFL }} \newcommand{\NP}{{\rm NP}} \renewcommand{\P}{{\rm P}} \newcommand{\IS}{{\rm ISAAC}} \newcommand{\lf}{\left\lfloor} \newcommand{\rf}{\right\rfloor} \newcommand{\lc}{\left\lceil} \newcommand{\rc}{\right\rceil} \newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\goes}{\rightarrow} \newcommand{\nth}{n^{th}} \newcommand{\N}{\sf{N}} \newcommand{\Q}{\sf{Q}} \newcommand{\R}{\sf{R}} \newcommand{\C}{\sf{C}} \newcommand{\Z}{\sf{Z}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\es}{\emptyset} \newcommand{\st}{\mathrel{:}} \newcommand{\e}{\varepsilon} \usepackage{tikz} \usetikzlibrary{automata,positioning,arrows} \begin{document} \centerline{\bf Homework 11 Morally Due May 7 at 3:30PM} \begin{enumerate} \item (25 points) In this problem we will guide you through a proof that the following problem is undecidable: Given a CFG $G$, is $\overline{L(G)}$ a CFL? We call this problem CFG-COMP. We define a variant of $\ACC_{e,x}$. {\it Def} For $e\in\N$, $\ACC_{e}$ is the set of all sequences of config's represented by $$ \$C_1 \$C_2^R \$C_3 \$C_4^R \$ \cdots \$ C_s^R \$ $$ such that \begin{itemize} \item $|C_1|=|C_2| = \cdots = |C_s|$. \item There is an $x$ such that $C_1,C_2,\ldots,C_s$ represents an accepting computation of $M_e(x)$. \end{itemize} \begin{enumerate} \item (5 points) Show that $\overline{ACC_e}$ is a context free grammar. (You only have to modify ONE of the parts of the CFG description for $\ACC_{e,x}$. The one having to do with the initial configuration. You do NOT have to rewrite the entire rest of the proof.) \item (0 points, so don't hand it in, just think about it.) Show that if $M_e$ accepts an INFINITE number of $x$ then $\ACC_e$ is NOT a CFL. (You may use the PL for CFG's.) \item (10 points) Show that if $M_e$ accepts a FINITE number of $x$ then $\ACC_e$ IS a CFL. \item (10 points) Let INF be the set of Turing machines that accept an INFINITE number of inputs. It is known that INF is undecidable (indeed!- its in $\Pi_2-\Sigma_1$). You may use this fact. Show that if CFG-COMP is decidable then INF is decidable. We give you some of the algorithm and BLANKS. You need to fill in the BLANKS. \begin{itemize} \item Input $e$. Create a CFG $G$ for $\overline{\ACC_e}$. \item BLANK \end{itemize} If $e\in\INF$ then BLANK hence the algorithm says YES. If $e\notin\INF$ then BLANK hence the algorithm says NO. \end{enumerate} \newpage \item (30 points- 10 points each) \begin{enumerate} \item Let $a_1,\ldots,a_k$ and $m_1,\ldots,m_k$ be natural numbers such that $(\forall i)[0\le a_i\le m_i]$. Show that the following set is Diophantine. What is the degree of the polynomial? What is the number of variables (including $x$). $$\biggl \{x \st \bigwedge_{i=1}^k x\equiv a_i \pmod {m_i} \biggr \}.$$ \item Let $a_1,\ldots,a_k$ and $m_1,\ldots,m_k$ be natural numbers such that $(\forall i)[0\le a_i\le m_i]$. Show that the following set is Diophantine. What is the degree of the polynomial? What is the number of variables (including $x$). $$\biggl \{x \st \bigvee_{i=1}^k x\equiv a_i \pmod {m_i} \biggr \}.$$ \item Let $p_1,\ldots,p_k$ be the first $k$ primes. Show that the following set is Diophantine. What is the degree of the polynomial? What is the number of variables (including $x$). $$\biggl \{ x \st \bigwedge_{i=1}^k x\not\equiv 0 \pmod {p_i}\biggr \}.$$ \end{enumerate} \newpage \item (20 points) Read or re-read the last part of the $(Q,<)$ slides-- the part about the horse number. The numbers $H(n)$ will come up in this problem. For $n\ge 2$. Let $B(n)$ be the number of ways that $n$ horses, $x_1,\ldots,x_n$, can finish a race (equalities allowed) such that $x_1