图灵机 - czk's wiki

定义：Turing机是五元组 $(K,\Sigma,\delta,s,H)$ ，其中

是状态的有穷集；
$\Sigma$ 是字母表，包含空格符 $\sqcup$ 和左端符 $\triangleright$ ，但不包含 $\leftarrow$ 和 $\rightarrow$ ，
$s\in K$ 是初始状态，
$H\subseteq K$ 是停机状态的集合，
$\delta$ 是转移函数，它是从 $(K-H)\times\Sigma$ 到 $K\times(\Sigma\cup\lbrace\leftarrow,\rightarrow\rbrace)$ 的函数，使得
1. 对所有 $q\in K-H$ ，若 $\delta(q,\triangleright)=(p,b)$ ，则 $b=\rightarrow$ ,
2. 对所有 $q\in K-H$ 和 $a\in\Sigma$ ，若 $\delta(q,a)=(p,b)$ ，则 $b\ne\triangleright$ 。

定义：Turing机 $M=(K,\Sigma,\delta,s,H)$ 的格局是 $K\times\triangleright\Sigma^*\times(\Sigma^*(\Sigma-\lbrace\sqcup\rbrace)\cup\lbrace e\rbrace)$ 。状态分量属于H的格局称为停机格局。

基本机器：

写符号机
向左移带头机
向右移带头机
向右找第一个 $\sqcup$ ： $R_\sqcup$
向左找第一个 $\sqcup$ ： $L_\sqcup$
向右找第一个非 $\sqcup$ ： $R_{\overline{\sqcup}}$
向左找第一个非 $\sqcup$ ： $L_{\overline{\sqcup}}$
复制机
左平移机 $S_\leftarrow$

定义：设 $M=(K,\Sigma,\delta,s,H)$ 是Turing机，使得 $H=\lbrace y,n \rbrace$ 包含两个不同的停机状态（ $y$ 和 $n$ 分别表示“是”和“否”）状态分量是 $y$ 的任何停机格局都称为接受格局。而状态分量是 $n$ 的停机格局称为拒绝格局。对输入 $w\in(\Sigma - \lbrace\sqcup,\triangleright\rbrace)^*$ ，若 $(s,\triangleright\underline{\sqcup}w)$ 产生接受格局则我们说M接受 $w$ ,若 $(s,\triangleright\underline{\sqcup}w)$ 产生拒绝格局则我们说M拒绝 $w$ 。

设 $\Sigma_0\subseteq(\Sigma-\lbrace\sqcup,\triangleright\rbrace)$ 是字母表，称为M的输入字母表；通过固定 $\Sigma_0$ 是 $\Sigma-\lbrace\cup,\triangleright\rbrace$ 的子集，我们允许Turing机在计算中使用除在输入里出现的符号外的额外符号。如果 $L\subseteq\Sigma_0^*$ 是语言，并且对任何字符串 $w\in\Sigma_0^*$ ，下列关系为真：若 $w\in L$ 则M接受 $w$ ；若 $w\notin L$ 则M拒绝 $w$ ，那么我们说 $M$ 判定语言 $L$ 。

若存在Turing机判定语言L则L称为递归的。即Turing机判定语言L的条件是，当在输入 $w$ 上启动时它总是停机并且停机状态是对输入的正确回答：若 $w\in L$ 则是 $y$ ，若 $w\notin L$ 则是 $n$ 。

定义：设 $M=(K,\Sigma,\delta,s,\lbrace h\rbrace)$ 是Turing机， $\Sigma_0\subseteq\Sigma-\lbrace\sqcup,\triangleright\rbrace$ 是字母表，并设 $w\in\Sigma_0^*$ 。假设 $M$ 在输入 $w$ 上停机，而且对某个 $y\in\Sigma_0^*$ ， $(s,\triangleright\underline{\sqcup}w)\vdash_M^*(h,\triangleright\underline{\sqcup}y)$ ，则 $y$ 称为 $M$ 在输入 $w$ 上的输出，并表示成 $M(w)$ 。

设 $f$ 是从 $\Sigma_0^*$ 到 $\Sigma_0^*$ 的任意函数。若对所有 $w\in\Sigma_0^*$ ， $M(w)=f(w)$ ，则我们说M计算函数f。即对所有 $w\in\Sigma_0^*$ ，M在输入 $w$ 上最终停机，并且当它确实停机时带上包含字符串 $\triangleright\sqcup f(w)$ 。若存在Turing机计算函数 $f$ ，则 $f$ 称为递归的。

定义：设 $M=(K,\Sigma,\delta,s,\lbrace h\rbrace)$ 是Turing机使得 $0,1,;\in\Sigma$ ，并设对某个 $k\geq 1$ ， $f$ 是从 $N^k$ 到 $N$ 的函数。若对所有 $w_1,\cdots,w_k\in 0 \bigcup 1(0\bigcup 1)^*$ ， $num(M(w_1;\cdots;w_k))=f(num(w_1),\cdots,num(w_k))$ ，则我们说 $M$ 计算函数 $f$ 。若存在计算函数 $f:N^k\mapsto N$ 的Turing机M，则 $f$ 称为递归的。

定义： $M=(K,\Sigma,\delta,s,H)$ 是Turing机， $\Sigma_0\subseteq\Sigma-\lbrace\sqcup,\triangleright\rbrace$ ，是字母表，并设 $L\subseteq\Sigma_0^*$ 是语言。若对任意字符串 $w\in\Sigma_0^*$ ，下列关系为真： $w\in L$ 当且仅当M在输入 $w$ 上停机，则我们说 $M$ 半判定 $L$ 。语言 $L$ 是递归可枚举的当且仅当存在Turing机 $M$ 半判定 $L$ 。

定理：若语言是递归的，则它是递归可枚举的。

定理：若L是递归语言，则它的补 $\overline{L}$ 也是递归的。

定理：如果非确定型Turing机M半判定或判定语言L或者计算函数f，则存在标准型Turing机M'半判定或者判定语言L或者计算函数f。

定义：文法是四元组 $G=(V,\Sigma,R,S)$ ，其中V是字母表； $\Sigma\subseteq V$ 是终结符集， $V-\Sigma$ 称为非终结符集； $S\in V-\Sigma$ 是起始符；并且规则集R是 $(V^*(V-\Sigma)V^*)\times(V^*)$ 的有穷子集。

任何上下文无关文法是文法。

定理：语言被文法生成当且仅当它是递归可枚举的。

定义：文法计算。函数 $f:\Sigma^*\mapsto\Sigma^*$ 是文法可计算当且仅当存在计算它的文法G。

定理：函数 $f:\Sigma^*\mapsto\Sigma^*$ 是递归的当且仅当他是文法可计算的。

定义：基本函数

定义：原始递归函数：

定义：极小化。可极小化的。

定义： $\mu$ 递归

定理：函数 $f:N^k\mapsto N$ 是 $\mu$ 递归的当且仅当它是递归的。