28
备注:
|
1987
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 1: | 行号 1: |
在这里详述 图灵机. | 定义:图灵机是五元组[[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\cup,\triangleright\rbrace)^*$$)]],若[[latex($$(s,\triangleright\underline{\cup}\omega)$$)]] |
定义:图灵机是五元组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
- 复制机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)$$)