%
% Assignment 5c for CS3530 Computational Theory:
% Computability
% Fall 2024
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{enumerate}

% skip for paragraphs, don't indent
\parskip 6pt plus 1pt
\parindent=0pt
\raggedbottom

% a list environment with no bullets or numbers
\newenvironment{indentlist}{\begin{list}{}{\addtolength{\itemsep}{0.5\baselineskip}}}{\end{list}}

\begin{document}
\begin{center}
\textbf{\Large CS 3530: Assignment 5c} \\[2mm]
Fall 2024
\end{center}

\raggedright

\section*{Problem 5.24}

Let $J = \{ w | $ either $w = 0x$ for some $x \in A_\text{TM}$, or $w = 1y$ for some $y \in \overline{A_\text{TM}} \}$.
Show that neither $J$ nor $\overline{J}$ is Turing-recognizable.

You must use reductions to get credit on this problem. This
means you should not assume $J$ is decidable, nor should you
construct a decider for $A_\text{TM}$, etc. You may not use Rice's
theorem.

Note that like Theorem 5.30 there will be two parts to this proof. In this assignment, you will solve the second part.

\subsection*{Problem (part 2) (20 points)}

Show that $\overline{J}$ is not Turing-recognizable by providing a reduction from $A_\text{TM}$ to $J$.  To complete your proof, you'll want to use the Definition 5.20 and Corollary 5.29.

\subsection*{Solution (part 2)}



\end{document}
