|
大小: 1000
备注:
|
大小: 1499
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 7: | 行号 7: |
| 定义：Turing机[[latex($$M=(K,\Sigma,\delta,s,H)$$)]]的格局是[[latex($$K\times\triangleright\Sigma^*\times(\Sigma^*(\Sigma-\lbrace\sqcup\rbrace)\cup\lbrace e\rbrace)$$)]]。状态分量属于H的格局称为停机格局。 | |
| 行号 9: | 行号 10: |
| * 写符号机[[latex($$\triangleright\leftarrow\rightarrow\sqcup$$)]] * 移带头机L和R * 向右找第一个a：Ra |
* 写符号机[[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}}$$)]] |
定义：图灵机是五元组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