CSCI3130 L09 Part 1 标准图灵机与函数

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L09 Part 1 标准图灵机与函数 · 原件 L09-图灵机-资料包.pdf（本地课件） p.1–97 定位：从读写头的单步语义学会识别、配置追踪和函数计算。 前后：下一份 L09-P2-图灵机组合.md

p.1 标题页；p.2 Outline。

本讲导航

1. P1 标准图灵机与函数：p.1–97。
2. P2 图灵机组合：p.98–103。
3. P3 图灵论题：p.104–109。
4. P4 真减法小测：p.110。

从识别到一般计算（p.3–5）【新】

p.3 引入Turing machine（TM），强调它不仅识别语言，也能计算输出。p.4 问三段等量与同向复制如何超越CFL；p.5 把它们放在TM可接受语言范围内。带子可反复读写，能回到先前标记的位置，不再受栈顶访问限制。

无限带子的单步操作（p.6–8）

p.6 有限控制与读写头连到带子；p.7 本讲带子向左右都无限，头每步左或右移一格。p.8 一个动作同时确定读到什么、写成什么、移动方向。无限带子表示没有预先固定存储上限，不表示某个有限时刻已实际访问无限格。

读写与初始布局（p.9–11）

p.9 在abac的第三格读a、写k、左移，带子abkc，头到b；p.10 读b写f右移，带子afkc，头回到k。写入只改当前格，不把整个后缀平移。p.11 输入是一段连续非空白字符，其外全空白，读头从输入最左格开始；空白符属于带字母表而非输入字母表。

本讲的非空输入约定（p.12–14）

p.12 Remark: the input string is never empty

p.12 暂设输入非空；后面题目有n≥0，包含空串时需明确扩展初态读空白的规则。p.13 $M=(Q,\Sigma,\Gamma,\delta,q_0,\diamond,F)$，$\Sigma\subseteq\Gamma$，空白 $\diamond\in\Gamma\setminus\Sigma$。p.14 边a,b,L表示读a、写b、左移，和PDA的“读、弹、压”三位置含义不同，不能混读。

转移函数与例子起点（p.15–17）

p.15 $\delta(q_1,a)=(q_2,b,R)$，函数输入只有状态与当前带符号；p.16 换c,d,L同样解释。p.17 图把头置于abac中的第三格a，执行前状态q1。带子上已有的辅助符号也可被读取，不限于原输入字母。

同样改写、不同方向（p.18–20）

p.18 a改b后右移，带子abbc，头到c；p.19 改写相同但左移，头到第二格b。p.20 读输入右侧第一空白写g右移，相当于扩展非空白区域。移动并不插入字符，之所以看似增长是原空白格被利用了。

p.20 还有一个版面错误需要区分：上一行写 abac，下一行写 abbcg，但所列边只会把当前空白改 g，不会同时改第三格 a。按本页这条边执行的正确带内容应是 abacg；若沿用 p.18 已改过的 abbc 作为输入，则可得到 abbcg。这里采用“每步只改当前格”的定义，不把无关格的变化计作机器能力。

确定、部分定义和停机（p.21–23）

p.21 同一状态读不同符号可有不同动作，同一状态读同一符号不可有两种；本讲标准机确定。没有“无需读格”的空转，每步始终看当前格，即使当前格为空白。p.22 转移可以未定义，p.23 无规则可走便停机。

接受、停机拒绝与不终止（p.24–26）

p.24 q1读c但仅列a、b规则，故停在非终态。p.25 终态不允许出边，到它就停机。p.26 把停在非终态和无限循环都归“不接受”的拒绝情况。术语补充：后续可计算性里通常把停机拒绝与发散区分；循环不是在有限时刻给出否定答案。识别器允许非成员上发散，判定器则所有输入都要停。

扫描纯 a 输入（p.27–29）

图（p.27）：q0读a保持a右移，读空白转终态q1并左移。讲义写接受 $aa^{\ast}$，这是沿用非空输入域；若也允许初始空串，现有空白边也会接受空串，变成 $a^{\ast}$。p.28 对aaa头在第一a，p.29 一步后第二a，带子不变。

到空白后接受（p.30–32）

p.30 头到第三a；p.31 再右移读头到右空白；p.32 走空白边左移回最后a，状态q1、无出边，接受。最终头位置与是否接受是两件事，此处左移是机器具体输出约定。

遇 b 停机拒绝（p.33–35）

p.33 输入aba，q0读首a右移；p.34 读b无规则，停机拒绝。p.35 若另加b,b,L自环，反而会在某些输入上循环；增加规则不一定让机器更快结束。

往返两格的无限循环（p.36–38）

p.36 头在aba的首a，读a右移到b；p.37 读b左移回首a；p.38 回到同一状态、同一带内容、同一头位置。因此未来会完全重演，无限循环已由完整配置重复证明，不能只靠“又看到a”断定。

证明停机与证明接受正确，需要不同的不变量（补充）：标记配对中，“每轮新增一对 X/Y”说明计数关系被保存；“未标 a 的数量每轮减少1且不为负”才说明外层循环不能无限重复。还要检查每轮的扫描会在有限距离遇到目标字符、边界或拒绝条件，否则外层只剩有限轮也可能在某轮里无限走。两层都有限，才得到总停机。

反过来，不接受并不总能在有限时刻被观察到。若一个模拟器已经跑了一百万步，尚未接受只说明前一百万步没有成功；若能证明完整配置重现，确定性才允许断言将永久重复。完整配置包括状态、头位置和所有非空带格，单独状态相同远远不够：扫描一长串 a 时状态会反复相同，却一直在前进并最终停机。

标记式等量识别（p.39–41）

p.39 展示往返重复，p.40 指出该运行永不接受。

题面（本讲 · Example 9.7 · p.41；公式按讲义重排）

p.41 Turing machine for the language $\{a^nb^n\}$.

图中q0把下一个a标x，q1右扫a、y，找第一个未标b改y，q2向左跨a、y回到x，再到q0处理下一a；q0若遇y表示a处理完，转q3检查剩余全为y，至空白进q4接受。符号x、y分别记已配对a、b。

p.41 原图的完整转移表，空白用 ◇，唯一终态 q4，未列情况均停机拒绝：

原图没有 q0 读空白的边，按非空输入约定识别 n≥1 的成员；若题目明确 n≥0，应另外加入 q0 读空白到接受态的规则，且不要给内部扫描态同样的快捷接受。

第一轮找 b（p.42–44）

p.42 对aabb初态q0在首a；p.43 首a改x、头右移到第二a；p.44 q1跨过第二a，头到首b。还没找到b前不能返回，否则只有a被标记、计数不一致。

标记 b 并返回（p.45–47）

p.45 首b改y，带xayb，q2左移到a；p.46 再左移到x；p.47 见x保持x右移并回q0，头在第二a，准备第二轮。回程停在最近的x，不必每次一直到最左空白。

第二轮完成配对（p.48–50）

p.48 第二a改x，带xxyb，q1到第一个y；p.49 跨y到末b；p.50 末b改y，带xxyy，q2左移。每轮新增恰一x、一y，已匹配数量始终相等。

发现没有未标 a（p.51–53）

p.51 q2跨y左行，p.52 到x后右移回q0，头现在指第一个y；p.53 q0遇y转q3并右移。此处不能立即接受，尚须检查右边没有多余b或乱序a。

最终检查与三段扩展（p.54–56）

p.54 q3越过第二y到空白，p.55 空白边到q4，13步接受aabb。p.56 说可扩展到三段等量：每轮标一个a、一个b、一个c，再回左端。这需要额外阶段和第三种标记，并检查整个输入次序，不能只给原机加一个c自环。

p.42–55 的 aabb 逐步运行表（方括号只标读头，不是带符号）：

配置中状态写在头前（p.57–59）【新】

p.57 配置 ca q1 ba 表示带内容caba，头读b。p.58 $q_2xayb\vdash xq_0ayb$ 表示在x上执行保持x右移，头到a。p.59 接着 $xq_0ayb\vdash xxq_1yb\vdash xxyq_1b$：先a改x，再跨y。状态符号不属于带子内容，只是把头的位置嵌入书写。

接受语言的定义（p.60–62）

p.60 $\vdash^{\ast}$ 表示若干步；无限循环对应无穷配置序列，不是某个“无限步之后”的终态。p.61 初始配置为q0w，p.62 $L(M)$ 收所有能经有限步到终态配置的w；最终带子可以已修改，不要求原输入仍在。

标准特征和两道构造小测（p.63–64）

p.63 汇总确定、双向无限带、带子兼作输入输出。

题面（本讲 · Short Quiz · p.64；公式按讲义重排）

p.64 Construct Turing machines that will accept the following languages

1. $L=\{a^nb^nc^n:n\ge0\}$

2. Even-length binary palindromes

第一题：先一扫检查a、b、c三段顺序；空输入单独接受。非空时每轮取最左未标a改X，向右取最左未标b改Y，再取最左未标c改Z，任一步缺失则拒绝；回左端重来。无a可取时，检查只剩标记，否则有多余b/c，拒绝。每轮减少三个未标字符，所以所有输入停机。补充演示aabbcc：一轮后XaYbZc，二轮后XXYYZZ，检查接受。

第二题：每轮找到最左未标位，记住其0/1于有限状态并擦成标记，右扫到最右未标位；若没有另一位则是奇数长度，拒绝；两位不同拒绝，相同则标记右位，返回左端。没有未标位时接受，包括空串。补充演示0110：外层0/0匹配，剩11；再匹配1/1，接受。010外层匹配后只剩中间1，拒绝。每轮减少两位，因此停机。完整有限控制可把“记住0”和“记住1”分别设状态，扫描动作只需对有限带字母分类。

p.65 Computing Functions分节页。

函数的编码先于机器（p.66–68）

p.66 函数有定义域D和输出集合，机器将w改成f(w)，称转导器。p.67 多参数如x+y，要编码成一条带上的有限串。p.68 数5可写十进制5、二进制101、一元11111。本讲用一元方便匹配，不表示不同编码的时间复杂度相同。

可计算要求在定义域内停机给正确输出（p.69–71）

p.69–70 对所有w∈D，从q0w经有限步到 $q_ff(w)$，通常要求头回到输出左端、带外恢复空白。对域外输入不在这个定义中保证结果。p.71 加法输入写 $1^x01^y$，输出 $1^{x+y}0$；0是分隔符，不是数值0的一元长度。

输出末尾的分隔符（p.72–74）

p.72 输入两个数字由0隔开，p.73 合并后把0放结果末尾，p.74 保留它供后续模块定位边界。因编码是 $1^{x+y}0$，输出不能只剩 $1^{x+y+1}$；中间0改成1后必须在末端再抵消一个1。

加法机的四个阶段（p.75–77）

图（p.75）：q0越过左数的1，遇0改1右移到q1；q1越过右数全部1，遇空白左移q2；q2把最后1改0左移q3；q3一路越1向左，遇空白右移进终态q4。p.76 例x=y=2，输入11011，最终11110，四个1表示4。p.77 起点在首1。

扫到分隔符并暂时多一个1（p.78–80）

p.78 跨第一个1，p.79 跨第二个1到0；p.80 把0改1，带11111，此时有5个1，只是中间状态，不能当最终加法结果。q1开始右扫剩余部分。

末端改回0（p.81–83）

p.81–82 q1跨完右数到空白，p.83 左移到最后1、状态q2。下一步才执行1→0；空白探测不能被误算为已改写最后1。

返回输出开头（p.84–86）

p.84 最后1改0，带11110，头左移在倒数第二格；p.85、86 q3连续左扫1，带不变。结果数值已正确，但还要满足头停在输出左端的接口约定。

最后归位（p.87–89）

p.87–88 继续左扫至左空白，p.89 右移到首1、进q4停机。完整11011过程共12次转移；末态接受与输出带内容都要检查，不能仅以“出现4个1”为验收标准。

p.77–89 的 11011 逐步运行表（方括号只标读头，不是带符号）：

一元翻倍的标记循环（p.90–92）

题面（本讲 · Example 9.10 · p.90；公式按讲义重排）

p.90 The function $f(x)=2x$ is computable.

p.91 输入 $1^x$，输出 $1^{2x}$。p.92 先把所有原1标为美元符号，再每轮找最右标记改回1、去右端追加一个1。只有原始标记才触发追加，新添的1不再被标记，因此不会无限自我复制。

翻倍图与比较函数（p.93–95）

p.93 q0右扫标记；q1向左跨已恢复的1，遇标记改1后进q2；q2向右到空白追加1，再回q1；q1最终遇左空白回到首格并进q3停机。p.94 输入11先变两个标记；第一轮形成“标记11”，第二轮形成1111，输出4，头归左。

题面（本讲 · Example 9.11 · p.95；公式按讲义重排）

p.95 The function $f(x,y)=1$ if $x>y$, $0$ if $x\le y$ is computable.

此处输出0/1是指定结果符号，区别于一元计数的空串编码，先确定约定再读机器。

p.93 翻倍图的全部规则：q0 读1写美元标记并右移留 q0，读空白保持并左移到 q1；q1 读1保持并左移留 q1，读美元标记改1并右移到 q2，读空白保持并右移到终态 q3；q2 读1保持并右移留 q2，读空白写1并左移回 q1。q3 无出边。q1 向左寻找的只有“未处理的原1标记”，所以新追加的1只能被跨过，不能再次触发复制。

比较通过成对消去实现（p.96–97）

p.96 输入仍 $1^x01^y$。p.97 每轮标记左数一个1及右数一个1；若左边先无未标1，x≤y，擦除工作区输出0；若右边先无未标1且左边尚有，x>y，输出1。补充算例（数字为演示自取）：x=3,y=2，两轮配完右数，左还剩1，输出1；x=y=2，两轮后左也无剩，输出0。检查顺序须把两边同时耗尽归入“≤”，不能误判为大于。

考试角度：（C 级 通识）常见考法是逐格执行带读写、写配置、证明标记循环的不变量和停机性，并区分函数输出与语言接受。

考试角度：（A 级：HW05-2025T1-题目.pdf Q3，对应二进制串反转。）见附录 A1。

考试角度：（A 级：Final-Exam-2023T1-题目.pdf Q7；期末-2023T1-资料包.pdf Q7，对应三段求和关系的TM转移图；扫描件视觉读取。）见附录 A2。

考试角度：（A 级：Final-Exam-2024T1-题目.pdf Q6；期末-2024未核-资料包.pdf Q6；Final-Exam-2025T1-题目.pdf Q5，对应小状态数TM识别正则模式；扫描件视觉读取。）见附录 A3。

本讲核心考点

• 读写移动、部分转移和停机（p.6–26，C 级）。
• 标记配对与配置表示（p.41–64，C 级）。
• 编码、输出接口及加法（p.66–89，C 级）。
• 翻倍和比较的有限循环（p.90–97，C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

A1 作业/往年题演练（非讲义内容）：HW05-2025T1-题目.pdf Q3

题面来自作业p.1；下面涉及辅导图及原解的页码均指 T07-2025T1.pdf（本地课件），不是作业的页码。完整过程同时写入本附录，便于在本讲练习。

题面块（HW05-2025T1-题目.pdf（本地课件） · Q3 · PDF p.1；与该辅导原题一致）：

p.1 Construct a Turing machine (Transition Graph or Transition Function) to compute the function: $f(w)=w^R$, where $w\in\{0,1\}^{+}$.

原解先把输入0/1改成x/y，随后每轮找最左未处理x/y，改为z，记住其比特，再到当前非空区左边的第一格空白写入该比特。处理顺序原本从左到右，输出每次添在已有输出左侧，所以顺序反转。z区最后擦除。

算一遍：输入101先变yxy。第一次把最左y标z，在左边写1，得到1zxy；第二次x标z并在已有1左边写0，得到01zzy；第三次y处理后得到101zzz；清理z得到101。为看出方向，自取输入110，依次输出1、11、011，最后是011，前导0必须保留。

完整状态图及输出归位（p.10）

图（p.10）：初态q0，终态q6，另有q1至q5。全部原图转移如下，□为空白；“保持”表示写回刚读的符号。

看什么：q2跳过已有输出0/1及已处理z，只有x/y触发新一轮；q5既擦z又越过输出至左边界，q6头最终回到输出最左格。不能只产出反转串而把z遗留在结果旁。

每轮未处理x/y数量减1，故n轮后进入清理并停机。第k轮完成后输出等于原串前k个字符的反转，这是正确性不变量。图在空输入上也可能停止，但题目函数域仅非空串；域外行为不影响本题，若要求拒绝空串，可新增起始检查再进入图中流程。原图使用双向无限带，本课程模型支持向输入左侧写输出。

回到正文：HW05-2025T1-题目.pdf Q3

A2 作业/往年题演练（非讲义内容）：三段求和关系的TM转移图

题面块（Final-Exam-2023T1-题目.pdf（本地课件） · Q7 · p.2；期末-2023T1-资料包.pdf（本地课件）同题，扫描件视觉读取）：

p.2 Draw the transition graph for a Turing Machine that accepts: $\{0^a1^b2^c\text{ with }a+c=b\}$

用X/Y/Z标记已处理的0/1/2。先验证0段、1段、2段的顺序，再给每个0配一个1，再给每个2配一个1，最后确认没有剩余1。下面用“起态，读→写，方向，终态”的表完全指定图；未列转移均停机拒绝，唯一终态F，无出边，□为空白。集合读符号表示各符号都各有同样规则并原样写回。

V态只检查格式，避免匹配算法误收乱序串。A/B/R每轮标一个0和一个1，找不到1则拒绝。C/D每轮标一个2并向左找尚未标记的1，找不到则拒绝。E只允许标记，故余下任何未配对1都拒绝。每成功轮消去一个0或2，数目有限，各扫描在有限非空区域内，所以总停机。

例001112：配两次0后XXYY12；再配一个2与最后1后XXYYYZ，E检查通过。00112在配0后XXYY2，处理2向左无剩余1，拒绝。λ通过格式扫描且没有债务，接受，对应a=b=c=0。这张表即转移图的逐边表示，不只给高层想法。

回到正文：三段求和关系的TM转移图

A3 作业/往年题演练（非讲义内容）：小状态数TM识别正则模式

题面块（Final-Exam-2024T1-题目.pdf（本地课件） · Q6 · p.1；期末-2024未核-资料包.pdf（本地课件）同题）：

p.1 Construct a Turing machine (transition graph or function) that accepts the language $L=\{aaaa^{\star}b^{\star}\}$. Assume that Σ = {a,b}.

原式为三个固定a后接a星，再接b星，即至少3个a、任意b。只右移不改写即可：q0读a→q1，q1读a→q2，q2读a→q3；q3读a留q3、读b到q4；q4读b留q4；q3/q4读□到F。所有上述动作原样写回并R，F唯一终态，未列在非终态无动作即拒绝。aaa、aaabb接受，aa拒绝，aaaba在q4读a拒绝。这个模型不必来回移动才能叫TM。

题面块（Final-Exam-2025T1-题目.pdf（本地课件） · Q5 · p.3）：

p.3 Construct a Turing machine (transition graph or function) that accepts the language

p.3 (a) [15 points] $L=\{ab(ba)^{\star}\}$. Assume that Σ = {a,b}. (≤ 6 states)

五态q0、q1、q2、q3、F，q0初始、F唯一终态。全部边：q0— a;a,R →q1；q1— b;b,R →q2；q2— b;b,R →q3；q3— a;a,R →q2；q2— □;□,R →F。其他无动作拒绝。q2对应完整读完初始ab及若干ba块，只有此时遇输入尾才接受。ab、abba、abbaba接受；aba、abb、abab拒绝。状态共5，未额外计不存在的显式拒绝态，满足≤6；若希望补显式拒绝态，可加一个成为6态。

回到正文：小状态数TM识别正则模式

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：L09-图灵机-资料包.pdf（本地课件），PDF p.1–97。

• 本次独立学习修订：核对本讲110页文本，视觉复核 p.20、41、55、75、93、101–103、105、110；按原转移表实际计算并验证13步配对、12步加法运行。