%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[12pt,oneside,english,english,english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{babel}
\usepackage{amssymb}
\usepackage[dvips]{color}
\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{plain}    
 \newtheorem{cor}[thm]{Corollary} %%Delete [thm] to re-start numbering
 \newtheorem{prop}[thm]{Proposition} %%Delete [thm] to re-start numbering
 \theoremstyle{definition}
 \newtheorem{defn}[thm]{Definition}
 \theoremstyle{definition}
 \newtheorem{example}[thm]{Example}
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\R}{\field{R}}
\newcommand{\Z}{\field{Z}}
\newcommand{\Q}{\field{Q}}
 \newcommand{\lyxaddress}[1]{
   \par {{\bf R}aggedright #1 
   \vspace{1.4em}
   \noindent\par}
 }


\begin{document}

\begin{center}
{\Large{\color{blue}Quiz 2}}
\end{center}
{\bf Instructions:} 
Show your work and explain every step. 


\begin{enumerate}

\item (3 points) Let $A$ be a language. Prove that $A$ is decidable iff $\overline{A}$ is decidable.

\vspace{.6 in}

\item (8 points) Decide if the following are true or false.

\begin{enumerate}

\item Every decidable language is Turing-recognizable.

\item For Turning machines, does not accept means reject.

\item Multi-tape Turing machines are equivalent to single tape Turing machines.

\item Non-determinist Turing machines are more powerful (i.e. recognize more languages) than 
deterministic Turing machines.

\item If $L$ is Turing recognizable, the $\overline{L}$ is Turning-recognizable.

\item A decidable problem is solvable by computers (i.e. has an lgorithm).

\item $E_{CFG}$ is decidable while $E_{TM}$ is not.

\item $EQ_{CFG}$ is undecidable.

\end{enumerate}

\item (4 points) Let $S=\{L~|~L \text{ is Turing-recognizable}\}$ and $\overline{S}=\{L~|~\overline{L} 
\text{ is Turing-recognizable}\}$. 

\begin{enumerate}

\item Find a bijection from $S$ to $\overline{S}$.

\vspace{.4 in}

\item Use the fact that $S \cup \overline{S}$ is countable, to prove there is a non Turing-recognizable language.

\vspace{.4 in}

\end{enumerate}

\item 

\begin{enumerate}

\item (3 points) Fill out the blanks:

A language is ........... iff both it and its complement are Turing-recognizable.

\item Use the first part to show that $\overline{A_{TM}}$ is not Turing-recognizable.

\vspace{.4 in}

\end{enumerate}

\item (2 points) Give the domain and the target for the tansition fiunction $\delta$ of deterministic Turing machines.


\end{enumerate}
\end{document}