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

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

基本机器:

定义:设$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$递归的当且仅当它是递归的。

图灵机 (last edited 2008-02-23 15:34:54 by localhost)

ch3n2k.com | Copyright (c) 2008 czk. 浙ICP备06000584号