图灵的计算理论与 Entscheidungsproblem 解决之道

本文档深入探讨了计算机科学先驱阿兰·麦席森·图灵（A.M. Turing）的思想与贡献，特别是他的工作在1936年发表的《可计算数与 Entscheidungsproblem 的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem）。文章从图灵的生平背景开始，讲述了他如何在那个科技相对落后的时代，面对复杂的编码难题，提出了划时代的理论。 首先，章节1介绍了“计算机器”，这是图灵理论的基础，他将机器的概念引入到数学和逻辑领域，探讨了机器的能力和局限性。他定义了自动机器和计算机器，区分了这两者在执行任务上的不同性质。 在定义部分，图灵引入了“圆周数”和“圆周自由数”的概念，这些是用于理解算法可执行性和复杂度的关键概念。他还讨论了“可计算序列和数”，这些都是后来发展成为计算机科学核心理论的重要元素。 接着，文章列举了几个具体的计算机器实例，通过实际操作来展示计算过程，并提供了简化的表格和进一步的例子，使读者能更好地理解抽象概念。 第5章和第6章着重于“可计算序列的枚举”，这涉及到如何确定哪些序列是可以由机器精确计算的。这部分的工作为现代计算机程序设计和算法分析奠定了基础。 然后，文章的核心部分——第7章，详细描述了通用计算机的概念，即“通用计算机器”。这是图灵提出的一种理论模型，它能够模拟任何其他计算机器，从而展示了计算能力的本质统一性。 最后，第8章应用了所谓的“对角线过程”，这是一种构造不可计算数的方法，这一过程对于证明某些问题无法被机器决定（即 Entscheidungsproblem）至关重要。图灵通过这个过程揭示了计算能力的边界，引发了计算机科学中关于算法、 decidability 和不可判定问题的广泛讨论。 此外，文档还提到了广告和免责声明，以及与网页相关的链接，包括Abelard网站上关于图灵论文的在线版本和Art&Logic Inc.的软件开发服务。这些内容虽然不是核心知识点，但反映了当时学术与商业环境的交织。 本文献是计算机科学史上的里程碑，通过探索图灵的理论，我们得以理解现代计算机科学中的基本概念和理论框架，如算法的界限、计算复杂性以及机器智能的基础。