如何在 Sipser 教科书中模仿图灵机描述

Question

计算理论简介经过西普瑟是计算理论的标准教科书之一。为了描述一个图灵机(TM) 在高层次上，这本书使用了一种非常独特的枚举列表变体。让我们看看我从教科书中扫描的例子。

• TM描述以机器名称开头，通常是大写英文字母。
• 机器名称后面跟着等号和引号。
• 描述的第一行解释了图灵机的输入是什么。
• 然后接下来的枚举列表给出了 TM 的实际高级描述。
• 有时，需要缩进来表示堵塞结构，如 TM 中的步骤 2 和 3埃来自上面的3.6。
• TM 描述以结束引号结束。

* 有时，我们需要在 TM 描述中引用特定步骤。例如，在上面的例子中，阶段 2、3 和 5 指向阶段 1。

---

作为这门课的助教，我想在我的课堂讲义中模仿这种结构。模仿这种 TM 描述的最佳方法是什么？

Answer 1

使用enumitem：

\documentclass{article}
\usepackage{amsmath}
\usepackage{enumitem}

\newenvironment{turing}[2]
 {\begin{enumerate}[leftmargin=0pt,labelsep=0pt,align=left,parsep=0pt]
  \item[$#1={}$]``\ignorespaces#2
  \begin{enumerate}[
    nosep,
    align=left,
    labelwidth=1.5em,
    label=\bfseries\arabic{*}.,
    ref=\arabic{*}
  ]}
 {\unskip''\end{enumerate}\end{enumerate}}

\newcommand{\bitem}{\item\hspace*{1em}\ignorespaces}

\begin{document}

\begin{turing}{E}{
  Ignore the input.
}
\item Repeat the following for $i=1,2,3,\dotsc$.
\bitem Run $M$ on $s_i$.
\bitem If it accepts, print out $s_i$.
\end{turing}

\begin{turing}{M_2}{
  On input string $w$:
}
\item Sweep left to right across the tape, crossing off every other \texttt{0}.\label{M2-sweep}
\item If in stage \ref{M2-sweep} the tape contained a single \texttt{0}, \emph{accept}.
\item If in stage \ref{M2-sweep} the tape contained more than a single \texttt{0}
  and the number of \texttt{0}s was odd, \emph{reject}.
\item Return the head to the left-hand end of the tape.
\item Go to stage \ref{M2-sweep}.
\end{turing}

\end{document}

Answer 2

\documentclass{article}

\begin{document}

\[
E=\parbox[t]{.75\textwidth}{%
``Solve the halting problem, $H$:
\begin{enumerate}
\item \label{x}do these until something
\addtolength\itemindent{1em}
\addtolength\labelsep{1em}
\item check if it halts
\item try it
\addtolength\itemindent{-1em}
\addtolength\labelsep{-1em}
\item test if stopped, if not repeat step \ref{x}''
\end{enumerate}}
\]
\end{document}