%% 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}Homework 7 (Reducibility and Decidability)}}

\vspace{.3 in}

{\it Due Friday, April 27, 07 at 3:00 PM in Class}
\end{center}

\vspace{1 in}

{\bf Note:} I may not grade all assignments and I may grade only selected problems from the assignment I garde.

\vspace{.3 in}

\begin{enumerate}

%\item Prove that if $A$ is Turing-recognizable and $A \leq_{m} \overline{A}$, then $A$ is decidable.

\item Prove that all Turing-recognizable languages are mapping reducible to $A_{TM}$. You have 
to mention the reduction function and to prove it's a reduction.

\item Give an example of an undecidable language $B$ such that $B \leq_{m} \overline{B}$. 
Give full explanation and show all details. Also, if your language was not shown in class to be 
undecidable, then you'll have to prove it's undecidable. You have also to mention the reduction 
function and to prove it's a reduction. 

\vspace{.5 in}

{\bf Note:} Next homework is on complexity classes.

\end{enumerate}


\end{document}
