图灵完备语言是什么

精选简答
如果一个计算机语言具有图灵完备性(Turing Completeness),那么这个语言就是图灵完备语言(Turing-complete language)。或者说,这个系统可以模拟通用图灵机。图灵完备性也可以用来描述计算机语言的计算能力。

回答

VIE
程序开发/运营

概述

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

背景

艾伦·图灵

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

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

图灵机

图灵机模型

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

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)。

可计算函数

艾伦·麦席森·图灵

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

A function is effectively calculable if its values can be found by some purely mechanical process.

如果一个函数的值可以通过某种纯机械的过程找到,那么这个函数就可以有效地计算出来。

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

图灵完备性

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

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

定义

图灵完备语言

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

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

过程式语言,如 FORTRAN、Pascal 等。

面向对象语言,如 Java、Python 等。

多范式语言,如 Ada、C++ 等。

使用不太常见范式的大多数语言:

函数式语言,如 Haskell、Mercury 等。

逻辑式语言,如 Logtalk、Prolog 等。

声明式语言,如 SQL、XSLT 等。

深奥的语言(Esoteric programming language),一种奇特的数学娱乐形式,程序员用极其困难但数学上图灵等价的语言来实现基本的编程结构。

非图灵完备语言

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

非图灵完备语言(Non-Turing-complete language),包括 HTML、JSON、XML、YAML 等。

更新时间:2021-02-18 12:39:53

该内容来源于合作方,未经允许请勿转载,如有侵权或合作请邮箱联系:mail@xzwk.cn

相关标签链接: