"图灵机"版本比较

定义：Turing机是五元组latex($$(K,\Sigma,\delta,s,H)$$)，其中 latex($$K$$)是状态的有穷集；latex($$\Sigma$$)是字母表，包含空格符latex($$\sqcup$$)和左端符latex($$\triangleright$$)，但不包含latex($$\leftarrow$$)和latex($$\rightarrow$$)， latex($$s\in K$$)K是初始状态，latex($$H\subseteq K$$)是停机状态的集合，latex($$\delta$$)是转移函数，它是从latex($$(K-H)\times\Sigma$$)到latex($$K\times(\Sigma\cup\lbrace\leftarrow,\rightarrow\rbrace)$$)的函数，使得

1. 对所有latex($$q\in K-H$$)，若latex($$\delta(q,\triangleright)=(p,b)$$)，则latex($$b=\rightarrow$$),

2. 对所有latex($$q\in K-H$$)和latex($$a\in\Sigma$$)，若latex($$\delta(q,a)=(p,b)$$)，则latex($$b\ne\triangleright$$)。

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

基本机器：

• 写符号机latex($$a$$)

• 向左移带头机L
• 向右移带头机R

• 向右找第一个latex($$\sqcup$$)：latex($$R_\sqcup$$)

• 向左找第一个latex($$\sqcup$$)：latex($$L_\sqcup$$)

• 向右找第一个非latex($$\sqcup$$)：latex($$R_{\overline{\sqcup}}$$)

• 向左找第一个非latex($$\sqcup$$)：latex($$R_{\overline{\sqcup}}$$)

• 复制机C

• 左平移机latex($$S_\leftarrow$$)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定义：基本函数

定义：原始递归函数：

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

定义：latex($$\mu$$)递归

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