评估语言“图灵完整性”的实用指南是什么?

您需要某种形式的动态分配构造( malloc 或 new 或 cons 可以),或者递归函数,或者其他编写无限循环的方法。如果你有这些并且能做任何有趣的事情,你几乎可以肯定图灵完成了。

lambda微积分相当于一个图灵机的功率,如果你实现lambda微积分,写lambda微积分程序实际上是相当有趣的。 方式 比为图灵机器编写程序更有趣!

我知道图灵完整性的唯一实际含义是,您可以编写不终止的程序。我使用了两种特殊用途的语言来保证终止,因此 不 图灵完成。有时,放弃额外的表达能力以换取有保证的终止是有用的。

'Turing Completeness' 描述能够表示任意 algorithmic computation, 这就是重点 Turing's Machine 首先。如果语言或逻辑系统具有此属性,则可以将其描述为“图灵完成”。从实践的角度来看,所有的通用编程语言——以及数量惊人的大量的专用编程语言——都可以这样做,以获得适当宽松的定义(见下文)。

然而,图灵完整性的严格定义意味着无限的存储容量,这在物理上是不可能的。考虑到这一点,没有物理机器可能是图灵完备的,但是当将图灵完备性归因于编程语言时,这种约束通常是宽松的(至少是非正式的)。对一种语言的图灵完整性的一个简单测试是该语言是否可以用于实现一个图灵机器模拟器。

关系代数(relational algebra)是一个广泛使用的非图灵完备系统的例子,它是在Codd的论文中描述的SQL背后的理论基础。 A relational model for large shared data banks. 关系代数具有 Godel Completeness 也就是说,它可以表示任何可以用 first-order predicate calculus (即普通逻辑表达式)。然而,它不是图灵完备的,因为它不能表达一个任意的算法计算。

请注意,大多数(如果不是所有)实用的SQL方言都使用过程构造扩展纯关系模型,直到它们按照通常应用于编程语言的定义图灵完成为止。但是,单个SQL查询(大体上来说)不是。

图灵完全领域特定语言的一些更令人震惊的例子是 TeX 和 sendmail.cf, . 在后一种情况下,实际上有一个著名的使用sendmail.cf to的示例 implement a universal Turing Machine simulator.

如果你能写 Brainf$&# 在你的语言中,它是图灵完备的。 LOLCODE 证明了图灵完全是这样的。

不图灵完备的语言的例子经常有 有界环 ,像:

for i=1 to N {...}

但缺乏 无界的 检查更一般情况的循环,例如:

while bool_expr {...}

如果所有可能的循环构造都是有界的,那么您的程序将被保证终止。而且,尽管无条件终止保证可能有用,但它也表明语言不是图灵完备的。

还要注意钉住 一切可能 循环构造可能是困难的,例如,我非常肯定C++模板不是打算图灵完成的。

我不确定是否有“最小功能集”,但是为了证明一种语言是图灵完备的,你只需要证明它可以模拟另一个图灵完备的系统(不一定是图灵机器),只要另一个系统是图灵完备的。 http://en.wikipedia.org/wiki/Turing_complete#Examples 有一个图灵完整系统的完整列表。其中一些比图灵机简单。

我想对诺曼·拉姆齐所说的话提出一个警告:图灵机器有无限的内存,因此被认为是图灵完备的编程语言只有在假设内存也是无限的情况下才是如此。

brainfuck是图灵完备的,它只有循环结构和内存递增/递减,所以这就足够了。

另一方面,在lambda演算中没有修改任何值的方法,但是它是图灵完备的,因此很明显,在没有可变内存的情况下进行修改是可能的。

很可能你的程序与lambda微积分无关,所以对于一个实际的答案,最小值必须是

1. 写入变量的方法
2. 一种读取变量的方法
3. 条件goto的一种形式(if语句、while循环等)

我不记得看到了什么 最小功能 为了图灵的完整性。然而,如果您的语言支持循环和条件分支,那么它是图灵完成的机会是很好的。然而,证明它的唯一方法仍然是模仿图灵机器或另一种图灵完整语言。

如果你能实现一个图灵机器(只要它们能被实现,因为它们是具有无限内存的数学构造[磁带大小是无限的]),那么你就可以确定它是图灵完成的。

一些迹象:

• 您可以检查内存并根据当前值对其进行操作,也可以使用它来控制程序流。
• 这个内存可以分配内存,可以附加到字符串,可以通过递归分配内存的堆栈等等。
• 程序流可以通过迭代或基于选择的递归来实现。

任何能够不终止的语言都是图灵完备的。您可以通过给语言提供无限循环结构(比如while循环或goto可以再次到达它自己),或者通过给它常规递归(让函数无限制地调用自己),使语言具有非终止功能。

曾经的你 是 图灵完成,你可以做一些像解释其他图灵完成语言一样的事情,包括你自己的。

真正的问题是“它有什么好处?”如果您的语言将被用于特定领域以解决特定的问题,那么最好找到一种方法,将解决方案用图灵不完整的语言表达出来,从而保证给出答案。

在任何其他图灵完整语言中,您都可以通过编写“Do this,that,or whatever;but do it with the result provided by x”(执行此操作、执行此操作或执行其他任何操作;其中x是由非图灵完整语言提供的)来添加图灵完整性。

当然,如果你只想使用一种语言,最好是图灵完备…

是否存在一组最小的特性,如果没有这些特性,图灵完整性是不可能实现的? 是否有一组功能实际上可以保证完整性?

是的,您需要有以数据为条件的控制流:通常表示为 if . 例如A +-*/ 袖珍计算器没有图灵完成,因为没有办法表达条件。

您还需要能够表示一个跳转回程序中较早的点,在此之上您可以实现一个循环。例如,禁止向后跳转以保证程序终止的BPF,也不是图灵全的。

您需要一些可读、可写和任意大的存储空间。例如,只有两个32位变量的语言在计算方面受到限制。对于存储的结构,您有许多选项:由指针、数组、堆栈、cons单元、纯数据结构等寻址的内存。

除此之外,您还可以构建其他所有编程语言:它可能不容易也不快,但已经足够了。

你可以尝试模仿 OISC (一台指令集计算机)。如果您可以模拟其中一个指令,那么由于这些单指令可以用来组成一个图灵完整机器,那么您已经证明了您的语言也必须是图灵完整的。

…比图灵完成的实际意义更重要。

我怀疑图灵完成有什么实际意义。

如果你看一些图灵完整机器的例子,例如原始机器 Turing machine ,您将看到,对于实际计算来说,它们远没有用处,因此概念必须只具有理论意义。