CSCI3130 L09 Part 3 图灵论题

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L09 Part 3 图灵论题 · 原件 L09-图灵机-资料包.pdf（本地课件） p.104–109 定位：说明后续使用图灵机形式化算法时所依赖的概念立场。 前后：上一份 L09-P2-图灵机组合.md · 下一份 L09-P4-真减法小测.md

p.104 Outline，进入图灵论题。

形式模型与直觉计算之间的主张（p.105–107）【新】

p.105 Any computation carried out by mechanical means can be performed by a Turing Machine

p.105 将“机械可执行的计算”与TM联系；p.106 用双向表述强调模型对有效计算的刻画。补充概念边界：这是论题而非仅靠形式定义可证明的定理，因为“机械可执行”的一侧是前形式直觉；对两个已严格定义的机器模型可以证明模拟等价，但那不等于证明这个总体论题。

p.107 本课程将计算函数的算法形式化为计算该函数的TM。这里关注可不可以完成，而非实际执行快不快；一个能模拟另一模型但慢得多的TM，在可计算性层面仍是等价模拟。

“存在算法”的形式含义（p.108–109）

p.108 后续说“存在算法”，可转成“存在执行相应任务的TM”。p.109 给出支持论题的课程陈述：已有数字计算机的任务可被TM模拟，其他机械计算模型也未带来更大可计算函数类。这是课件的论述，本伴读未将其历史日期或措辞另作外部史料核验。

不能把论题理解为“所有数学问题都有算法”，也不能理解为“所有接受语言的TM都停机”。它说明有效算法能放入这个模型；正因模型明确，后面才可以证明某些任务不存在这样的算法。

考试角度：（C 级 通识）常见考法是区分可计算性与效率，以及模型等价定理和关于有效计算的论题。

使用论题时，不要把“任务”悄悄换掉（补充）

“输入一个有限整数，逐一尝试它的因数直到找到或试完”是一套明确有限步骤，因此可以进一步编码成 TM；“等到某个永远不会发生的事件，再报告没有事件”却没有给出有效停止规则。后者不能只贴上“理想计算机”标签便称为算法。模型允许无界但每一步有限的工作，不提供预知未来的判定动作。

三个结论可以顺次拆开：先证明两种严格定义的机器可互相模拟，得到相同可计算范围；再讨论直觉上有效过程是否被这些模型捕获，这是论题层次；最后分析某种模拟的步数膨胀，这是复杂性层次。模拟花平方时间还是指数时间，不改变第一层的可计算包含，却会深刻影响第三层。课件说“机械计算可模拟”不能自动升级为“所有合理物理装置都可高效模拟”。

课件原陈述的三项范围（p.105–109）

p.105 把论题旁标为“1930”，本讲 p.3 又将图灵机模型标为1936；这里保留其为课件年代标注，不把前者当作已经核实的提出年份。p.106 的“No known model ... more powerful”讨论的是有效机械计算模型，不包括给机器额外赠送不可计算答案的预言机。p.109 三条支持理由分别是数字计算机可模拟、直觉算法尚无反例、其他机械模型能力吻合；它们支持课程采用 TM 作为算法模型，不构成把非形式概念转成数学定理的证明。

本讲核心考点

• 机械计算与TM的对应主张（p.105–106，C 级）。
• 算法存在、停机保证和效率的区别（p.107–109，C 级）。

附录

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

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.104–109。

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