%
% Assignment 5a for CS3530 Computational Theory:
% Computability
% Fall 2023
%
% 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 5a} \\[2mm]
Fall 2023
\end{center}

\raggedright

\section*{Problem 5.9 (10 points)}

\subsection*{Problem}

Let $T=\{\langle M\rangle| M$ is a TM that accepts $w^\mathcal{R}$
whenever it accepts $w\}$. Show that $T$ is undecidable.

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

\subsection*{Solution}


\section*{Problem 5.13 (10 points)}

\subsection*{Problem}

A \textit{useless state} in a Turing machine is one that is never
entered on any input string. Consider the problem of determining
whether a Turing machine has any useless states. Formulate this
problem as a language and show that it is undecidable.

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

\subsection*{Solution}


\end{document}
