图灵机

返回“计算理论”

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

• \(K\)是状态的有穷集；
• \(\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的格局称为停机格局。

基本机器：

• 写符号机\(a\)
• 向左移带头机\(L\)
• 向右移带头机\(R\)
• 向右找第一个\(\sqcup\)：\(R_\sqcup\)
• 向左找第一个\(\sqcup\)：\(L_\sqcup\)
• 向右找第一个非\(\sqcup\)：\(R_{\overline{\sqcup}}\)
• 向左找第一个非\(\sqcup\)：\(L_{\overline{\sqcup}}\)
• 复制机\(C\)
• 左平移机\(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\)递归的当且仅当它是递归的。