图灵完备语言 Turing-Complete Language

概述

如果一个计算机语言具有图灵完备性(Turing Completeness),那么这个语言就是图灵完备语言(Turing-Complete Language)。

背景

艾伦图灵

图灵完备语言 Turing-Complete Language

艾伦麦席森图灵(Alan Mathison Turing,1912.6.23 - 1_ 8 z 1954.6.7),1 英国数学家、逻辑学家h H = N ! 8 D 密码学家和英国首位计算机科学家,被誉为计算机科学和人工智能之父。2

他对计算机科; k v Z学的发展有着很高的影响力,他用图灵机提供了算法和计; g ] A算概念的形式化,图灵机可以被视为通用计算机的模型{ k &3 他的图灵测试对人工智能的发展,作出了重要的、典型的、具挑? _ R 5 2战性的和持久的贡献。4

图灵机

在 1928 年第八届国际数学家大会上,德国数/ @ U r学家希尔伯特(David Hilbert,1862 - 1943)提出了D Z j 3关于数学的三个精辟问题:

First, was mathematics complete ...(数学是完K _ h n & n备的吗?)
Second, was mathematics consistent ...(f k Q ( ^ H h i数学是一致的吗?)
And thirdly, was mD m : S @ B fathematics decidable ?(数学是可判定的吗?)

图灵完备语言 Turing-Complete Language

希尔伯特的第三个问题又被称为判定c R . = m t Y性问题(Entsche_ b E Q !idungsproblem)。为了证G ` _ % : ` ( _ {否这个命题,1936C Q j d a - ~ } 年,图灵发表了一篇论文,题为《论可计算数,及其在判定性问题上的应用》(On Computable Numbers, with an Applicati; 6 ) 4 a U @ oon to the Entscheidungsproblem)。在这篇论文里,图灵提出了一种假设的k o F 7计算装置,他称之为 A-Machine(Automatic Machine,自动机器),这就是图灵机(Turing Machine)。

可计算函数

1938 年,在美国普林斯顿大学攻读博士学位的图灵,发表了一篇 6 4 | 9 ]博士论文,题为《基于序数的逻辑系统》(Sl M 7 0 Dystems of Logic Based on Ordinals)。在这篇论文里,图灵定义了可计算函数(Computable Function):

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

在作为特定计算模型的图灵机上产生的可计算函u G 6 : W数,就被称为图灵可计算函数

定义

具有图灵完备性的计算机语言,就被称为图灵完备语言。绝大多数的编程语言,都是图灵完备语言。这包K h , X B括:

  • 广泛使用的所有通用语言:

    • 过程式语言,如 FORTRAN、Pascal 等。
    • 面向对象语言,如 Java、Python 等。
    • 多范式语言,如 Ada、X = Z g 2C++ 等。
  • 使用不太常见范式的大I ^ a + S 0 # $多数语言:

    • 函数式语言,如 Haskell、Mercury 等。
    • 逻辑式语言,如 Logtalk、Prolog 等。
    • 声明式语言,如 SQL、XSLT 等。
    • 深奥的语言(Esoteric Programming Language),一种奇特的数学娱乐形式,程序员用极其困难w ? K 2 / j但数学上图灵等Q : D B 7 } ) ? G价的语言来实现基本的编程结构。

非图灵完备语言

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

非图灵完备语言(Non-Turing-Complete Language),包括 Hf 9 & L + + GTML、O [ 6 p G D $ oJSON、XML、YAML 等。


  1. 艾伦图灵——如谜的解I a s U谜者 -# i U 8 ( / 4 K j 科学松鼠会 ↩
  2. 148 封图灵文~ / , y件重现 - 澎湃新闻 ↩
  3. 计算的极限(零):逻辑与图灵机 - 科学松鼠会 ↩
  4. “人工智能之父”图灵登上 50 英镑纸钞 -7 7 k J @ 澎湃新闻 ↩