2165
备注:
|
4028
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 4: | 行号 4: |
(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$$)]]。 |
1. 对所有[[latex($$q\in K-H$$)]],若[[latex($$\delta(q,\triangleright)=(p,b)$$)]],则[[latex($$b=\rightarrow$$)]], 1. 对所有[[latex($$q\in K-H$$)]]和[[latex($$a\in\Sigma$$)]],若[[latex($$\delta(q,a)=(p,b)$$)]],则[[latex($$b\ne\triangleright$$)]]。 |
行号 21: | 行号 21: |
设[[latex($$\Sigma_0\subseteq(\Sigma-\lbrace\cup,\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\cup,\triangleright\rbrace$$)]]是字母表,并设[[latex($$\omega\in\Simga_0^*$$)]]。假设M在输入[[latex($$\omega$$)]]上停机,而且对某个[[latex($$y\in\Simga_0^*$$)]],[[latex($$(s,\triangleright\underline{\cup}\omega)\vdash_M^*(h,\triangleright\underline{\cup}y)$$)]],则y称为M在输入[[latex($$\omega$$)]]上的输出,并表示成[[latex($$M(\omega)$$)]]。 设f是从[[latex($$\Simga_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\cup\f(\omega)$$)]]。若存在Turing机计算函数f,则f称为递归的。 |
定义:图灵机是五元组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)$$)的函数,使得
对所有latex($$q\in K-H$$),若latex($$\delta(q,\triangleright)=(p,b)$$),则latex($$b=\rightarrow$$),
对所有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
- 复制机C
定义:设latex($$M=(K,\Sigma,\delta,s,H)$$)是Turing机,使得latex($$H=\lbrace y,n \rbrace$$)包含两个不同的停机状态(y和n分别表示“是”和“否”)状态分量是y的任何停机格局都称为接受格局。而状态分量是n的停机格局称为拒绝格局。对输入latex($$\omega\in(\Sigma - \lbrace\cup,\triangleright\rbrace)^*$$),若latex($$(s,\triangleright\underline{\cup}\omega)$$)产生接受格局则我们说M接受latex($$\omega$$),若latex($$(s,\triangleright\underline{\cup}\omega)$$)产生拒绝格局则我们说M拒绝latex($$\omega$$)。
设latex($$\Sigma_0\subseteq(\Sigma-\lbrace\cup,\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\cup,\triangleright\rbrace$$)是字母表,并设latex($$\omega\in\Simga_0^*$$)。假设M在输入latex($$\omega$$)上停机,而且对某个latex($$y\in\Simga_0^*$$),latex($$(s,\triangleright\underline{\cup}\omega)\vdash_M^*(h,\triangleright\underline{\cup}y)$$),则y称为M在输入latex($$\omega$$)上的输出,并表示成latex($$M(\omega)$$)。
设f是从latex($$\Simga_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\cup\f(\omega)$$)。若存在Turing机计算函数f,则f称为递归的。