|
大小: 583
备注:
|
大小: 1000
备注:
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 1: | 行号 1: |
| 定义：图灵机是五元组(K, ∑, δ, s, H)，其中 K是状态的有穷集；∑是字母表，包含空格符和左端符，但不包含←和→，s∈K是初始状态，H⊆K是停机状态的集合，δ是转移函数，它是从(K-H)×∑到K×(∑∪{←, →})的函数，使得 (1)对所有q∈K-H，若δ(q,) = (p,b)，则b=→ (2)对所有q∈K-H和a∈∑，若δ(q,a)=(p,b)，则b≠ |
定义：图灵机是五元组[[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$$)]]。 |
| 行号 7: | 行号 9: |
| * 写符号机a | * 写符号机[[latex($$\triangleright\leftarrow\rightarrow\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$$)。
基本机器：
- 移带头机L和R
- 向右找第一个a：Ra
- 复制机C