图灵完备语言

　　　　　　2024 年 4 月 27 日 星期六

中文名称 图灵完备语言 语言特征 具有图灵完备性 汉语拼音 Túlíng Wánbèi Yǔyán 包　　括 过程式语言、面向对象语言、多范式语言、 英文名称 Turing-complete language 深奥的语言等

图灵完备语言

概述

　　如果一个计算机语言具有图灵完备性（Turing completeness），那么这个语言就是图灵完备语言（Turing-complete language）。

{Top}

背景

艾伦·麦席森·图灵

艾伦·图灵

　　艾伦·麦席森·图灵（Alan Mathison Turing，1912.6.23 - 1954.6.7），[1] 英国数学家、逻辑学家、密码学家和英国首位计算机科学家，被誉为计算机科学和人工智能之父。[2]

　　他对计算机科学的发展有着很高的影响力，他用图灵机提供了算法和计算概念的形式化，图灵机可以被视为通用计算机的模型。[3] 他的图灵测试对人工智能的发展，作出了重要的、典型的、具挑战性的和持久的贡献。[4]

{Top}

图灵机

　　在 1928 年第八届国际数学家大会上，德国数学家希尔伯特（David Hilbert，1862 - 1943）提出了关于数学的三个精辟问题：[5]

• First, was mathematics complete …（数学是完备的吗？）
• Second, was mathematics consistent …（数学是一致的吗？）
• And thirdly, was mathematics decidable ?（数学是可判定的吗？）

图灵机的模型

　　希尔伯特的第三个问题又被称为判定性问题（Entscheidungsproblem）。为了证否这个命题，1936 年，图灵发表了一篇论文，题为《论可计算数，及其在判定性问题上的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem）。在这篇论文里，图灵提出了一种假设的计算装置，他称之为 A-Machine（Automatic Machine，自动机器），这就是图灵机（Turing machine）。[6]

{Top}

可计算函数

　　1938 年，在美国普林斯顿大学攻读博士学位的图灵，发表了一篇博士论文，题为《基于序数的逻辑系统》（Systems of Logic Based on Ordinals）。在这篇论文里，图灵定义了可计算函数（Computable function）：[7]

• A function is effectively calculable if its values can be found by some purely mechanical process.
• 如果一个函数的值可以通过某种纯机械的过程找到，那么这个函数就可以有效地计算出来。

　　在作为特定计算模型的图灵机上产生的可计算函数，就被称为图灵可计算函数。[8]

{Top}

图灵完备性

　　如果一个计算系统可以计算每一个图灵可计算函数，那么这个系统就是图灵完备的；或者说，这个系统可以模拟通用图灵机。[9]

　　图灵完备性也可以用来描述计算机语言的计算能力。

{Top}

定义

　　具有图灵完备性的计算机语言，就被称为图灵完备语言。绝大多数的编程语言，都是图灵完备语言。这包括：[10]

• 广泛使用的所有通用语言：
  • 过程式语言，如 FORTRAN、Pascal 等。
  • 面向对象语言，如 Java、Python 等。
  • 多范式语言，如 Ada、C++ 等。
• 使用不太常见范式的大多数语言：
  • 函数式语言，如 Haskell、Mercury 等。
  • 逻辑式语言，如 Logtalk、Prolog 等。
  • 声明式语言，如 SQL、XSLT 等。
  • 深奥的语言（Esoteric programming language），一种奇特的数学娱乐形式，程序员用极其困难但数学上图灵等价的语言来实现基本的编程结构。

{Top}

非图灵完备语言

　　并非所有的计算机语言都是图灵完备的，例如标记语言，或者更恰当地称为“容器语言”或“数据描述语言”，就不是图灵完备的。[11]

　　非图灵完备语言（Non-Turing-complete language），包括 HTML、JSON、XML、YAML 等。

{Top}

参考资料

1. {⇧} Alan Turing - Infogalactic
2. {⇧} 艾伦·图灵——如谜的解谜者 - 科学松鼠会
3. {⇧} 148 封图灵文件重现 - 澎湃新闻
4. {⇧} “人工智能之父”图灵登上 50 英镑纸钞 - 澎湃新闻
5. {⇧} 计算的极限（零）：逻辑与图灵机 - 科学松鼠会
6. {⇧} Turing machine - Infogalactic
7. {⇧} Alan Turing's a-(automatic-)machine - Infogalactic
8. {⇧} Computable function - Infogalactic
9. {⇧} Turing completeness - Infogalactic
10. {⇧} Examples - Infogalactic
11. {⇧} Non-Turing-complete languages - Infogalactic

{Top}