\documentclass[a4paper]{article}
\usepackage[en-GB]{datetime2}
\usepackage{sansmath, amsmath, hyperref}

\setlength\fboxsep{2ex}
\setlength\parskip{2ex}
\setlength\parindent{0pt}

\DeclareMathOperator\enc{e}
\DeclareMathOperator\lang{L}

\newcommand\decisionproblem[4]{%
    \begingroup\centering\fbox{%
        \parbox{\dimexpr\linewidth-2\fboxsep-1pt\relax}{%
            \setlength\parskip{1em}
            \underline{#1~({\sffamily\sansmath #2})}
            \par
            \begin{tabular}{@{}ll}
                \textsl{Input} & #3; \\
                \textsl{Question} & #4
            \end{tabular}
        }%
    }\endgroup%
}

\title{THE3 Standard Decision Problems}
\author{Oliver Dixon}

\makeatletter
\let\authorname\@author
\makeatother
\newcommand\authoremail{\href{mailto:od641@york.ac.uk}{od641@york.ac.uk}}

\begin{document}
\begingroup
    \setlength\parskip{0pt}
    \maketitle
\endgroup

\decisionproblem{Halting Problem}{HP}
    {A Turing machine $ M $ and a string $ w \in \Sigma^* $}
    {Does $ M $ halt on $ w $?}

\decisionproblem{$ \Lambda $-Halting Problem}{$ \Lambda $-HP}
    {A Turing machine $ M $}
    {Does $ M $ halt on $ \Lambda $?}

\decisionproblem{\textit{abc}-Halting Problem}{abc-HP}
    {A Turing machine $ M $}
    {Does $ M $ halt on \textit{abc}?}

\decisionproblem{Uniform Halting Problem}{UHP}
    {A Turing machine $ M $}
    {Does $ M $ halt on all inputs $ w \in \Sigma^* $?}

\decisionproblem{Self-Accepting Problem}{SAP}
    {A Turing machine $ M $}
    {Is $ \enc(M) \in \lang(M) $?}

\decisionproblem{Membership Problem for Semidecidable Languages}{MP}
    {A Turing machine $ M $ and a string $ w \in \Sigma^* $}
    {Is $ w \in \lang(M) $?}

\decisionproblem{Accept-$ \Lambda $ Problem}{A-$ \Lambda $}
    {A Turing machine $ M $}
    {Is $ \Lambda \in \lang(M) $?}

\decisionproblem{Accept-All Problem}{AAP}
    {A Turing machine $ M $}
    {Is $ \lang(M) = \Sigma^* $?}

\decisionproblem{Emptiness Problem}{EP}
    {A Turing machine $ M $}
    {Is $ \lang(M) = \emptyset $?}

\decisionproblem{Equivalence Problem}{EQP}
    {Turing machines $ M_1 $ and $ M_2 $}
    {Is $ \lang\left(M_1\right) = \lang\left(M_2\right) $?}

\decisionproblem{Inclusion Problem}{IP}
    {Turing machines $ M_1 $ and $ M_2 $}
    {Is $ \lang\left(M_1\right) \subseteq \lang\left(M_2\right) $?}

\decisionproblem{Property Problem (c.f.~Rice's Theorem)}{$ P $-P}
    {A Turing machine $ M $}
    {Does $ M $ have the property $ P $?}

\begin{center}
    End of Decision Problems
\end{center}
\vfill
More variations on these problems can be found in the THE3 lecture notes, but
the ones listed here are the most important. The author of this document is
\authorname~and may be contacted via e-mail at \authoremail.
\end{document}

